환형 연결 리스트 (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;
}
}
환형 연결 리스트는 노드들이 순환하는 구조로 되어있으므로 다른 연결 리스트보다 포인터에 신중을 기해야 한다.
그리고 지정된 노드에서 앞, 뒤로 어떤 노드로 이동할 수 있으므로 어떻게 보면 더 쉽게 삽입, 삭제가 이루어 질 수 있다.