자료구조에서 연결 리스트(Linked List)는 데이터 요소들의 선형 집합입니다. 리스트의 각 요소, 즉 노드(node)는 두 가지 항목으로 구성됩니다. 바로 데이터와 다음 노드를 가리키는 참조(포인터)입니다. 마지막 노드는 null을 참조하며, 연결 리스트의 진입점은 헤드(head)라고 부릅니다.
단일 연결 리스트(singly linked list)에서 각 노드는 자신의 데이터와 함께 다음 노드를 가리키는 포인터만 저장합니다. 즉, 이전 노드를 가리키는 포인터나 참조는 존재하지 않습니다.
순환 연결 리스트(circular linked list)는 마지막 노드가 null이 아닌 헤드를 다시 가리키는 구조로, 리스트가 하나의 원처럼 이어져 있습니다.
이 글에서 다룰 것은 정렬된 순환 단일 연결 리스트입니다. 이름 그대로 리스트에 삽입되는 모든 데이터는 항상 정렬된 상태를 유지합니다. 새로운 값이 삽입될 때마다 올바른 위치를 찾아 배치되기 때문에, 언제든지 오름차순으로 순회할 수 있습니다.
알고리즘
시작
createnode() 함수 — 리스트에 노드 삽입:
리스트가 비어 있는지 확인한다.
리스트가 비어 있으면 해당 노드를 첫 번째 요소로 넣고 head를 갱신한다.
리스트가 비어 있지 않으면,
새 노드(newnode)를 생성하고 데이터 필드에 값을 넣는다.
새 노드는 연결 리스트가 항상 정렬 상태를 유지하도록 적절한 위치에 삽입된다.
마지막에 삽입되는 경우, 새 노드는 head를 가리킨다.
첫 번째 위치에 삽입되는 경우, 연결 리스트는 그 지점부터 시작하도록 head를 갱신한다.
끝
시작
display() 함수 — n개의 노드를 가진 리스트 내용 출력:
c = 0으로 초기화한다.
포인터 변수를 시작 주소(head)로 초기화한다.
while (c <= n)
노드 정보를 출력한다.
포인터 변수를 다음 노드로 갱신한다.
c를 1 증가시킨다.
끝예제 코드
#include<iostream>
using namespace std;
struct nod {
int d;
nod *n;
}
*p = NULL, *head = NULL, *q = NULL, *np = NULL;
int c = 0;
void createnode(int n) {
np = new nod;
np->d = n;
np->n = NULL;
if (c == 0) { // 첫 번째 노드 삽입
head = np;
p = head;
p->n = head; // 순환 구조: 자기 자신을 가리킴
c++;
} else if (c == 1) { // 두 번째 노드 삽입
p = head;
q = p;
if (np->d < p->d) { // 새 값이 더 작으면 head 앞에 삽입
np->n = p;
head = np;
p->n = np;
} else if (np->d > p->d) { // 새 값이 더 크면 뒤에 삽입
p->n = np;
np->n = head;
}
c++;
} else { // 세 번째 노드부터
p = head;
q = p;
if (np->d < p->d) { // head보다 작으면 맨 앞 삽입 후 tail 재연결
np->n = p;
head = np;
do {
p = p->n;
} while (p->n != q);
p->n = head;
} else if (np->d > p->d) { // 정렬 위치를 찾아 중간 또는 끝에 삽입
while (p->n != head && q->d < np->d) {
q = p;
p = p->n;
if (p->n == head) { // 마지막 위치에 도달한 경우
p->n = np;
np->n = head;
} else if (np->d < p->d) { // 중간에 삽입하는 경우
q->n = np;
np->n = p;
break;
}
}
}
}
}
void display(int i) {
nod *t = head;
int c = 0;
while (c <= i ) { // 순환 구조 확인을 위해 한 노드를 더 출력
cout<<t->d<<" ";
t = t->n;
c++;
}
}
int main() {
int i = 0, n, a;
cout<<"노드 개수 입력
";
cin>>n;
while (i < n) {
cout<<"
노드 값 입력
";
cin>>a;
createnode(a);
i++;
}
cout<<"정렬된 순환 단일 연결 리스트"<<endl;
display(n);
}실행 결과
노드 개수 입력 5 노드 값 입력 6 노드 값 입력 4 노드 값 입력 7 노드 값 입력 3 노드 값 입력 2 정렬된 순환 단일 연결 리스트 2 3 4 6 7 2
코드 설명
위 코드의 동작을 단계별로 살펴보면 다음과 같습니다.
1. 첫 번째 노드 삽입 (c == 0): 새 노드가 곧 head가 되며, 순환 구조를 만들기 위해 자기 자신을 가리키도록 설정합니다.
2. 두 번째 노드 삽입 (c == 1): 새 값이 기존 head의 값보다 작으면 head 앞에 삽입하고 head를 갱신하고, 크면 head 뒤에 삽입한 뒤 head를 가리켜 순환을 완성합니다.
3. 세 번째 노드부터: 세 가지 경우로 나뉩니다.
- 새 값이 head보다 작은 경우 → 맨 앞에 삽입한 후, 마지막 노드(tail)를 찾아 새 head를 가리키도록 재연결합니다.
- 중간에 들어가야 하는 경우 → 앞 노드(q)와 현재 노드(p) 사이에 삽입합니다.
- 모든 값보다 큰 경우 → 마지막 노드 뒤에 삽입하고 head를 가리켜 순환을 유지합니다.
display() 함수는 의도적으로 노드 수보다 하나 더 많이 출력합니다(c <= i). 이렇게 하면 마지막에 head의 값이 다시 나타나므로, 리스트가 실제로 순환(circular) 구조임을 눈으로 확인할 수 있습니다.
출력 결과에서 2 3 4 6 7까지 정렬된 값이 표시된 뒤 2(head 값)가 한 번 더 출력되는 것을 통해, 마지막 노드가 다시 head로 연결되어 있는 순환 구조임을 알 수 있습니다.