환형 연결 리스트 (Circular Linked List)

연결 리스트 (Linked List)와 이중 연결 리스트 (Doubly Linked List)에 대한 설명은 이미 포스팅 되어 있으므로 생략하겠다.

환형 연결 리스트는 아래의 그림을 보면 이해하기 쉬울 것이다.

<그림1> 이중 연결 리스트

<그림2> 환형 연결 리스트

위 그림에서 보시다시피, 이중 연결 리스트와 노드 형태는 같다. 하지만 HEAD 노드의 PrevNode 와 TAIL 노드의 NextNode 를

사용한다는 점이 다르다. 이러한 구조의 장점은 시작을 알면 끝을 알 수 있고, 끝을 알면 시작을 알 수 있다는 점이다.

새로운 노드를 붙일 때 TAIL 노드를 찾기 위한 비용이 거의 없어진다는 의미와 같다.

환형 연결 리스트의 주요 연산은 다른 연결 리스트와 같지만 염두에 두어야 할 것이 있다.

첫 번째, TAIL은 HEAD의 '앞 노드'이다.

두 번째, HEAD는 TAIL의 '뒷 노드'이다.

주의 깊게 살펴봐야 할 노드 추가와 삭제 연산만 보도록 하겠다.

• 노드 추가

void appendNode(Node** Head, Node* newNode) {

if( (*Head) == NULL ) {

*Head = newNode;

(*Head)->NextNode = *Head;

(*Head)->PrevNode = *Head;

} else {

Node* Tail = (*Head)->PrevNode;

Tail->NextNode->PrevNode = newNode;

Tail->NextNode = newNode;

newNode->NextNode = (*Head);

newNode->PrevNode = Tail;

}

}

위 코드를 설명하자면, Head 노드가 NULL 이면 포인터를 모두 Head를 가리키게 하고,

그렇지 않으면 우선 Tail의 노드에 접근 한 뒤 Head 노드의 PrevNode 에 newNode 그리고 Tail 노드의 NextNode 에 newNode를

가리키게 한다. 그런 다음 newNode 에 대한 NextNode와 PrevNode 를 Head와 Tail를 가리키게 한다.

• 노드 삭제

void removeNode(Node** Head, Node* remove) {

if( *Head == remove) {

(*Head)->PrevNode->NextNode = remove->NextNode;

(*Head)->NextNode->PrevNode = remove->PrevNode;

*Head = Remove->NextNode;

 remove->NextNode = NULL;

 remove->PrevNode = NULL;

} else {

Node* temp = remove;

remove->PrevNode->NextNode = temp->NextNode;

remove->NextNode->PrevNode = temp->PrevNode;

remove->NextNode = NULL;

remove->PrevNode = NULL;

}

}

환형 연결 리스트는 노드들이 순환하는 구조로 되어있으므로 다른 연결 리스트보다 포인터에 신중을 기해야 한다.

그리고 지정된 노드에서 앞, 뒤로 어떤 노드로 이동할 수 있으므로 어떻게 보면 더 쉽게 삽입, 삭제가 이루어 질 수 있다.