순환 단일 연결 리스트란?
순환 단일 연결 리스트(Circular Singly Linked List)는 자기 참조 구조체(self-referential structure)를 이용해 생성한 노드들로 구성되는 자료구조입니다. 각 노드는 두 부분으로 나뉘는데, 하나는 실제 데이터를 저장하는 데이터(data) 영역이고, 다른 하나는 다음 노드를 가리키는 포인터(next)입니다.
연결 리스트 전체에 접근하려면 첫 번째 노드에 대한 참조만 있으면 되며, 이를 헤드(head)라고 부릅니다. 일반 연결 리스트와 달리 순환 연결 리스트는 마지막 노드가 리스트의 첫 번째 노드, 즉 헤드를 다시 가리킵니다. 바로 이러한 순환 구조 때문에 '순환(circular) 연결 리스트'라는 이름이 붙었습니다.
아래는 C++로 순환 단일 연결 리스트를 구현한 전체 예제 코드입니다.
예제 코드
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
do {
cout<<ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The circular linked list is: ";
display();
return 0;
}
실행 결과
The circular linked list is: 9 2 7 1 3
출력 결과를 보면 삽입된 순서(3, 1, 7, 2, 9)와 반대로 값이 출력되는 것을 확인할 수 있습니다. 이는 insert() 함수가 항상 리스트의 맨 앞(head)에 새 노드를 추가하기 때문입니다.
코드 상세 분석
1. 노드 구조체 정의
위 프로그램에서 Node 구조체는 연결 리스트의 개별 노드를 표현합니다. 정수형 데이터와 다음 노드를 가리키는 포인터로 구성되어 있습니다.
struct Node {
int data;
struct Node *next;
};2. insert() 함수 — 노드 삽입
insert() 함수는 새로운 데이터를 연결 리스트의 맨 앞에 삽입합니다. 먼저 새 노드(newnode)를 동적 할당으로 생성하고, 매개변수로 받은 값을 노드의 data 필드에 저장합니다.
- 헤드가 NULL인 경우(빈 리스트): 새 노드는 자기 자신을 가리켜 스스로 순환 구조를 형성합니다.
- 헤드가 NULL이 아닌 경우: 마지막 노드까지 이동한 뒤, 마지막 노드의 next가 새 노드를 가리키도록 변경합니다.
마지막으로 head가 새 노드를 가리키게 하여 삽입이 완료됩니다.
void insert(int newdata) {
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
struct Node *ptr = head;
newnode->data = newdata;
newnode->next = head;
if (head!= NULL) {
while (ptr->next != head)
ptr = ptr->next;
ptr->next = newnode;
} else
newnode->next = newnode;
head = newnode;
}3. display() 함수 — 리스트 출력
display() 함수는 연결 리스트 전체를 화면에 출력합니다. 포인터 ptr이 헤드를 가리킨 후, do-while 반복문을 통해 각 노드의 데이터를 출력하며 다음 노드로 계속 이동합니다. ptr이 다시 헤드로 돌아오면 한 바퀴를 모두 돌았다는 의미이므로 반복을 종료합니다.
void display() {
struct Node* ptr;
ptr = head;
do {
cout<< ptr->data <<" ";
ptr = ptr->next;
} while(ptr != head);
}4. main() 함수 — 프로그램 실행 흐름
main() 함수에서는 insert()를 여러 번 호출해 순환 연결 리스트에 값을 차례로 삽입한 뒤, display()를 호출하여 전체 리스트를 출력합니다.
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The circular linked list is: ";
display();
return 0;
}마무리
순환 단일 연결 리스트는 마지막 노드가 헤드를 가리키는 특징 덕분에 라운드 로빈(Round Robin) 스케줄링, 멀티플레이어 게임의 턴 관리 등 끝없이 순회해야 하는 상황에서 유용하게 활용됩니다. 위 예제를 직접 컴파일하고 실행하면서 노드 삽입과 순회 과정을 익혀보시기 바랍니다.