Page 382 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

typedef struct __node {
Member data; /* 데이터 */
struct __node *prev; /* 앞쪽 노드에 대한 포인터 */
struct __node *next; /* 다음 노드에 대한 포인터 */
} Dnode;

Dnode
prev

data
next
[그림 9-19] 이중 연결 리스트의 노드 구성

머리 노드인지 판단하는 방법

이때 Dnode *형 변수 p가 리스트의 어떤 노드를 가리키는 경우 p가 가리키는 노드가 이중 연
결 리스트의 머리 노드인지 판단하려면 다음 식을 사용합니다.
다음 두 가지 방법 중 하나만 사용하면 됩니다.

p == list->head /* p가 가리키는 노드가 머리 노드인지 확인합니다. */
p->prev == NULL /* p가 가리키는 노드가 머리 노드인지 확인합니다. */

꼬리 노드인지 판단하는 방법
또 p가 가리키고 있는 노드가 꼬리 노드인지 판단하려면 다음 식을 사용합니다.

p->next == NULL /* p가 가리키는 노드가 꼬리 노드인지 확인합니다. */

원형 이중 연결 리스트

그러면 바로 앞에서 공부한 두 가지의 개념을 합한 원형 이중 연결 리스트(circular doubly
linked list)에 대해 알아보겠습니다.

꼬리 노드를 가리킵니다.
head

A B C D E F

머리 노드를 가리킵니다.

[그림 9-20] 원형 이중 연결 리스트

382 C 알고리즘