원형 연결 리스트 (Circular Linked List)
원형 연결 리스트란?
연결 리스트에서는 노드와 연결 리스트의 개념, 그리고 구현 방법을 살펴보았다.
이때 head와 tail, 더미 노드를 함께 관리하는 단방향 연결 리스트를 구현했다.
단방향 연결 리스트에서는 마지막 노드의 next가 NULL을 가리키므로 시작과 끝이 분명하다.
단방향 원형 연결 리스트에서는 마지막 노드의 next가 NULL 대신 첫 번째 노드를 가리킨다.
이로써 모든 노드가 끊김 없이 연결되는 순환 구조가 만들어진다.
그림으로 두 연결 리스트의 구조를 비교해 보자.
Singly Linked List
[head] ---> [10 | next] ---> [20 | next] ---> [30 | next] ---> NULL
^
[tail]
Circular Linked List
+---------------------------------+
| |
v |
[10 | next] ---> [20 | next] ---> [30 | next]
^
[tail]원형 연결 리스트는 모든 노드가 원형으로 연결되어 있어 고정된 시작과 끝이 없다.
하지만 기준이 없으면 삽입과 삭제 등의 연산을 어느 노드에서 시작할지 정하기 어려워 구현이 불편하다.
이 글에서는 마지막 노드를 가리키는 tail을 기준점으로 삼아 구현한다.
그림을 보면 마지막 노드의 next 포인터를 연결하는 것만으로 원형 연결 리스트를 구현할 수 있으므로, 구현 자체는 어렵지 않아 보인다.
더 궁금한 점은 연결 리스트를 순환 구조로 만들었을 때 어떤 이점을 얻을 수 있는가 하는 점이다.
단방향 연결 리스트에서 head만 관리하면 마지막 노드를 찾기 위해 처음부터 순회해야 하므로, 맨 뒤에 원소를 삽입하는 작업이 불편하다.
그래서 마지막 노드에 빠르게 접근하기 위해 tail을 두고, 맨 앞의 삽입과 삭제를 단순하게 처리하기 위해 더미 노드도 사용했다.
원형 연결 리스트에서는 마지막 노드인 tail의 next가 첫 번째 노드를 가리킨다.
따라서 tail 하나만 관리해도 마지막 노드에는 tail로, 첫 번째 노드에는 논리적인 head인 tail->next로 접근할 수 있다.
이러한 구현상의 장점 외에도 원형 연결 리스트는 순환 순회가 필요한 상황에 알맞다.
라운드 로빈 방식의 작업 스케줄링, 반복 재생 목록, 턴제 게임 등에서는 마지막 다음이 첫 번째라는 규칙을 자연스럽게 표현할 수 있다.
소스 코드
아래 코드는 학습용 코드로, 핵심 동작에 집중하기 위해 메모리 할당이 성공하고 각 함수가 올바른 순서로 호출된다고 가정한다.
main.c
#include <stdio.h>
#include "circular_linked_list.h"
void print_list(List* list, int repeat_count)
{
ListData data;
int total_count = list_size(list) * repeat_count;
printf("List (size: %d)\n", list_size(list));
printf(" data: ");
if (list_first(list, &data))
{
printf("%d", data);
for (int i = 1; i < total_count; i++)
{
if (list_next(list, &data))
printf(", %d", data);
}
}
printf("\n");
}
int main(void)
{
List list;
ListData data;
/* 1. Initialize the circular linked list. */
list_init(&list);
/* 2. Insert data at the back and front of the list. */
list_append(&list, 3);
list_append(&list, 4);
list_append(&list, 5);
list_prepend(&list, 2);
list_prepend(&list, 1);
print_list(&list, 3);
/* 3. Remove every even number from the list. */
int node_count = list_size(&list);
list_first(&list, &data);
if (data % 2 == 0)
list_remove_current(&list, &data);
for (int i = 1; i < node_count; i++)
{
list_next(&list, &data);
if (data % 2 == 0)
list_remove_current(&list, &data);
}
print_list(&list, 1);
/* 4. Release the list nodes. */
list_destroy(&list);
return 0;
}circular_linked_list.h
#ifndef CIRCULAR_LINKED_LIST_H
#define CIRCULAR_LINKED_LIST_H
#include <stdbool.h>
typedef int ListData;
typedef struct Node
{
ListData data;
struct Node* next;
} Node;
typedef struct CircularLinkedList
{
Node* tail;
Node* previous;
Node* current;
int size;
} CircularLinkedList;
typedef CircularLinkedList List;
bool list_init(List* list);
void list_destroy(List* list);
int list_size(const List* list);
/* Insertion operations */
bool list_prepend(List* list, ListData data);
bool list_append(List* list, ListData data);
/* Cursor-based iteration */
bool list_first(List* list, ListData* out_data);
bool list_next(List* list, ListData* out_data);
bool list_remove_current(List* list, ListData* out_data);
#endif /* CIRCULAR_LINKED_LIST_H */circular_linked_list.c
#include <stdlib.h>
#include "circular_linked_list.h"
bool list_init(List* list)
{
if (list == NULL)
return false;
list->tail = NULL;
list->previous = NULL;
list->current = NULL;
list->size = 0;
return true;
}
void list_destroy(List* list)
{
Node* current;
Node* next;
if (list == NULL || list->tail == NULL)
return;
current = list->tail->next;
list->tail->next = NULL;
while (current != NULL)
{
next = current->next;
free(current);
current = next;
}
list->tail = NULL;
list->previous = NULL;
list->current = NULL;
list->size = 0;
}
int list_size(const List* list)
{
return list->size;
}
bool list_prepend(List* list, ListData data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
if (list->tail == NULL)
{
list->tail = new_node;
new_node->next = new_node;
}
else
{
new_node->next = list->tail->next;
list->tail->next = new_node;
}
list->size++;
return true;
}
bool list_append(List* list, ListData data)
{
Node* new_node = (Node*)malloc(sizeof(Node));
new_node->data = data;
if (list->tail == NULL)
{
list->tail = new_node;
new_node->next = new_node;
}
else
{
new_node->next = list->tail->next;
list->tail->next = new_node;
list->tail = new_node;
}
list->size++;
return true;
}
bool list_first(List* list, ListData* out_data)
{
if (list->tail == NULL)
return false;
list->previous = list->tail;
list->current = list->tail->next;
*out_data = list->current->data;
return true;
}
bool list_next(List* list, ListData* out_data)
{
if (list->tail == NULL)
return false;
list->previous = list->current;
list->current = list->current->next;
*out_data = list->current->data;
return true;
}
bool list_remove_current(List* list, ListData* out_data)
{
Node* del_node = list->current;
*out_data = del_node->data;
if (del_node == list->tail)
{
if (list->tail == list->tail->next)
list->tail = NULL;
else
list->tail = list->previous;
}
list->previous->next = list->current->next;
list->current = list->previous;
if (list->tail == NULL)
{
list->previous = NULL;
list->current = NULL;
}
free(del_node);
list->size--;
return true;
}삽입 연산
일반 단방향 연결 리스트에서는 맨 앞 삽입과 맨 뒤 삽입이 서로 다른 작업이다.
연결 리스트의 시작과 끝이 서로 멀리 떨어진, 별개의 위치이기 때문이다.
원형 연결 리스트에서는 마지막 노드가 첫 번째 노드를 가리키므로, 맨 앞과 맨 뒤는 연결 경계에서 맞닿아 있다.
어디를 시작이나 끝이라 부를지는 구현을 위한 기준일 뿐이다.
원을 하나 그려 놓고 어디를 “시작”과 “끝”이라 부를지는 관점의 문제일 뿐인 것처럼 말이다.
노드의 연결 형태만 보면, 맨 앞 삽입과 맨 뒤 삽입은 모두 tail과 첫 번째 노드 사이에 새 노드를 끼워 넣는 동일한 작업이다.
여기서 첫 번째 노드는 논리적인 head인 tail->next다.
list_prepend와 list_append의 유일한 차이는 list_append가 새 노드를 마지막 노드로 취급하기 위해 tail을 갱신한다는 점이다.
빈 리스트에 삽입
먼저 두 함수에서 같은 부분, 빈 리스트에 첫 번째 노드를 삽입하는 경우를 살펴보자.
Before insertion
NULL <--- [tail]
After insertion
+------------------------------+
| |
v |
[10 | next] -----------------------+
^
|
[tail]tail이 새 노드를 가리키도록 한다.
이어서 새 노드의 next가 자기 자신을 가리키게 하여 원형 연결을 만든다.
맨 앞 삽입 (list_prepend)
리스트가 비어 있지 않은 상태에서 list_prepend를 호출한다고 가정한다.
Before
+-------------------------------------------------+
| |
v |
[10 | next] ---> [20 | next] ---> [30 | next] --------+
^
|
[tail]
After
+--------------------------------------------------------------+
| |
v |
[5 | next] ---> [10 | next] ---> [20 | next] ---> [30 | next] ----+
^
|
[tail]새 노드의 next가 기존 첫 번째 노드인 tail->next를 가리키도록 한다.
그다음 tail->next를 새 노드로 바꾸면 새 노드가 첫 번째 노드가 된다.
맨 뒤 삽입 (list_append)
리스트가 비어 있지 않은 상태에서 list_append를 호출한다고 가정한다.
Before
+-------------------------------------------------+
| |
v |
[10 | next] ---> [20 | next] ---> [30 | next] --------+
^
|
[tail]
After
+--------------------------------------------------------------+
| |
v |
[10 | next] ---> [20 | next] ---> [30 | next] ---> [40 | next] ----+
^
|
[tail]새 노드의 next가 기존 첫 번째 노드인 tail->next를 가리키도록 한다.
그다음 tail->next가 새 노드를 가리키도록 한다.
list_prepend와 달리 list_append는 tail을 새 노드로 갱신한다.
새 노드가 새로운 마지막 노드가 되면서 삽입이 완료된다.
삭제 연산
이 구현에서는 list_first와 list_next로 순회한 뒤 list_remove_current로 현재 노드를 삭제한다.
마지막 노드가 삭제 대상이고 노드가 하나뿐인 경우
삭제할 노드가 하나뿐이라면 tail은 그 노드를 가리킨다.
그 노드의 next는 자기 자신을 가리킨다.
따라서 이 노드를 삭제하면 리스트는 빈 상태가 된다.
초기 상태인 빈 리스트로 되돌리려면 tail을 NULL로 바꾸고, 순회를 위해 사용하던 previous와 current도 NULL로 초기화하면 된다.
그다음 삭제할 노드를 free()로 해제하고, 리스트의 크기를 하나 줄이면 삭제가 완료된다.
마지막 노드가 삭제 대상이고 노드가 둘 이상인 경우
마지막 노드가 삭제 대상이라면 tail은 그 노드를 가리킨다.
삭제할 노드는 나중에 해제할 수 있도록 지역 변수에 따로 저장한다.
그다음 tail이 previous를 가리키도록 바꾸면, 이전 노드가 새로운 마지막 노드가 된다.
previous->next가 current->next를 가리키도록 바꾸면, 이전 노드와 다음 노드가 직접 연결되어 삭제할 노드는 리스트에서 제외된다.
마지막으로 삭제할 노드를 free()로 해제하고, 리스트의 크기를 하나 줄이면 삭제가 완료된다.
마지막 노드가 삭제 대상이 아닌 경우
삭제 대상이 마지막 노드가 아닌 경우에는 tail을 갱신할 필요가 없다.
바로 앞에서 설명한 것처럼 삭제할 노드를 연결에서 제외한 뒤 해제하면 된다.