다음 C 코드에 10개의 노드로 이루어진 이중 연결 리스트를 입력하여 … | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지

다음 C 코드에 10개의 노드로 이루어진 이중 연결 리스트를 입력하여 수행한 후, 이중 연결 리스트에 남아 있는 노드의 개수는? (단, 10개 노드 입력 후 수행 시 start는 첫 번째 노드를 가리킨다)
typedef struct node {
  int key;
  struct node *prev, *next;
} node;

void foobar(node *start) {
    node *current = start;
    int iseven = 0;
    while(current != NULL) {
      if(iseven == 1) {
        current->prev->next = current->next;
        if(current->next != NULL)
          current->next->prev = current->prev;
      }
      current = current->next;
      iseven = 1 - iseven;
    }
}

5

6

8

10

수행 후 남는 노드는 5개이다.
iseven은 0과 1을 번갈아 가지며, 1일 때 현재 노드의 앞뒤 노드를 직접 연결해 현재 노드를 건너뛰게(삭제) 만든다. 첫 노드는 iseven = 0이므로 남는다.
삭제된 노드의 next는 그대로라 current = current->next로 다음 노드에 정상 진행하므로, 두 번째·네 번째·…·열 번째의 짝수째 노드 다섯 개가 삭제되고 홀수째 다섯 개가 남는다.
6개: 열 번째 노드도 짝수째라 삭제되므로 남는 수는 다섯이다.
8개: 두 개만 지우는 경우인데, 반복은 리스트 끝까지 계속된다.
10개: 삭제가 없는 경우인데, iseven이 번갈아 1이 되므로 삭제가 일어난다.