정답
① struct Node *, ② p = p->rlink, ③ phead->llink->rlink = newnode, 출력 결과: 20 30 15 10 5
출제 의도
원형 이중연결리스트의 구조를 이해하고, 노드를 head 기준 왼쪽·오른쪽에 삽입하는 포인터 연산을 정확히 구현할 수 있는지 평가하는 문제이다. 또한 순환 리스트를 오른쪽 방향으로 순회하며 데이터를 출력하는 반복문을 완성하고, 삽입 연산 후 리스트에 저장된 데이터의 순서를 추적하는 능력을 확인한다.
풀이 과정
먼저 구조체 정의 부분에서 llink, rlink는 이전 노드와 다음 노드를 가리키는 포인터이다. 구조체 안에서는 typedef 이름인 \( \text{DListNode} \)를 사용할 수 없고, 태그 이름인 \( \text{struct Node} \)를 사용해야 하므로 포인터 형은 struct Node *가 되어야 한다. 따라서 ①에는 struct Node *가 공통으로 들어간다.
printDlist() 함수의 for 문을 보면, p는 phead->rlink에서 시작하여 p != phead일 동안 오른쪽 링크(rlink)를 따라가며 출력해야 한다. 따라서 증감식에는 현재 노드에서 오른쪽 노드로 이동하는 코드 p = p->rlink가 들어가야 한다. 이것이 ②이다.
dinsertLeft() 함수는 새 노드를 head의 왼쪽, 즉 원형 리스트에서 head 바로 왼쪽 위치(맨 끝 노드와 head 사이)에 삽입하는 함수이다. 새 노드의 포인터 연산을 살펴보면, 먼저
새 노드의 오른쪽 링크를 head로, 왼쪽 링크를 기존의 head 왼쪽 노드로 설정한다.
$$ \text{newnode->rlink} = \text{phead}, \quad \text{newnode->llink} = \text{phead->llink} $$
이제 기존의 마지막 노드(삽입 전 phead->llink)가 가리키는 오른쪽 링크를 새 노드로 바꾸어 주어야 새 노드가 리스트에 연결된다. 즉,
$$ \text{phead->llink->rlink} = \text{newnode} $$
가 되어야 하고, 이것이 ③에 해당하는 코드이다. 그 다음 문장 phead->llink = newnode;로 head의 왼쪽 링크를 새 노드로 갱신하면 삽입이 완료된다.
이제 main 함수에서 리스트가 어떻게 만들어지는지 순서를 따라가 보자.
초기화 후 리스트는 head만 있는 상태이다.
1. dinsertRight(head, 10) 실행 후: 오른쪽에 10 삽입
리스트: head ↔ 10 ↔ head
2. dinsertRight(head, 15) 실행 후: head 오른쪽에 15 삽입
리스트: head ↔ 15 ↔ 10 ↔ head
3. dinsertRight(head, 30) 실행 후
리스트: head ↔ 30 ↔ 15 ↔ 10 ↔ head
4. dinsertRight(head, 20) 실행 후
리스트: head ↔ 20 ↔ 30 ↔ 15 ↔ 10 ↔ head
5. dinsertLeft(head, 5) 실행 후: head 왼쪽(맨 끝)에 5 삽입
리스트: head ↔ 20 ↔ 30 ↔ 15 ↔ 10 ↔ 5 ↔ head
마지막으로 printDlist(head)는 p = head->rlink에서 시작하여 head를 다시 만날 때까지 오른쪽으로 이동하며 각 노드의 data를 출력한다. 따라서 출력되는 순서는
$$ 20,\ 30,\ 15,\ 10,\ 5 $$
가 되고, 실제 출력 결과는 공백을 포함하여 20 30 15 10 5가 된다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>