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

09-4 원형 이중 연결 리스트

이번에는 원형 이중 연결 리스트에 대해 살펴보겠습니다.

원형 리스트

그림 9-17과 같이 선형 리스트의 꼬리 노드가 머리 노드를 가리키면 원형 리스트(circular list)라
고 합니다. 원형 리스트는 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조입니다.

head
머리 노드를 가리킵니다.
A B C D E F

[그림 9-17] 원형 리스트

원형 리스트와 선형 리스트의 차이점은 꼬리 노드의 다음 노드를 가리키는 포인터가 널
(NULL)이 아니라 머리 노드의 포인터 값이라는 점입니다. 원형 리스트는 선형 리스트에서 사
용했던 것과 같은 자료형을 사용할 수 있습니다. 또한 앞으로는 리스트를 관리하는 구조체 포
인터를 list라고 하겠습니다. 그러면 먼저 원형 리스트에서 발생할 수 있는 리스트의 상태를

판단하는 방법을 알아보겠습니다.

빈 원형 리스트를 판단하는 방법

노드가 없는(비어 있는) 원형 리스트인지 판단하려면 다음 식을 사용합니다.

list->head == NULL /* 선형 리스트가 비어 있는지 확인합니다. */

노드가 1개인 원형 리스트를 판단하는 방법

노드가 1개라면 머리 노드의 다음 포인터는 자기 자신인 머리 노드를 가리킵니다. 노드가 1개
인 원형 리스트인지 판단하려면 다음 식을 사용합니다.

list->head->next == list->head /* 노드가 1개인지 확인합니다. */

380 C 알고리즘