순환 이중 연결 리스트란?
자료구조에서 연결 리스트(Linked List)는 데이터 요소들이 선형으로 연결된 집합입니다. 리스트의 각 요소, 즉 노드(node)는 두 부분으로 구성됩니다. 하나는 실제 저장되는 데이터이고, 다른 하나는 다음 노드를 가리키는 참조(포인터)입니다. 마지막 노드는 null을 참조하며, 연결 리스트의 진입점(entry point)을 헤드(head)라고 부릅니다.
순환 이중 연결 리스트(Circular Doubly Linked List)에서는 인접한 두 요소가 이전(prev) 포인터와 다음(next) 포인터로 양방향으로 연결됩니다. 여기에 더해 마지막 노드의 next 포인터는 첫 번째 노드를 가리키고, 첫 번째 노드의 prev 포인터는 마지막 노드를 가리킵니다. 덕분에 리스트 전체가 하나의 원처럼 순환하는 구조를 이루게 됩니다.
정렬된 순환 이중 연결 리스트는 노드의 데이터 필드에 담긴 모든 값이 항상 일정한 순서(오름차순)를 유지하는 리스트입니다. 따라서 새 노드를 삽입할 때마다 적절한 위치에 배치하여 정렬 상태가 깨지지 않도록 관리해야 합니다.
알고리즘
시작
circulardoublylist 클래스를 생성하고 다음 함수들을 포함시킨다:
nod *create_node(int) = 노드에 필요한 메모리를 동적으로 할당한다.
insert_begin() = 리스트의 맨 앞에 요소를 삽입한다.
리스트가 비어 있으면 노드를 삽입하고 next, prev 포인터를 NULL로 설정한다.
리스트가 비어 있지 않으면 데이터를 삽입하고 next, prev 포인터를 설정한 뒤 갱신한다.
insert_end() = 리스트의 맨 끝에 요소를 삽입한다.
리스트가 비어 있으면 순환 이중 연결 리스트 형태의 노드를 생성한다.
마지막 노드를 찾는다.
노드를 동적으로 생성한다.
새 노드의 next가 시작 노드(start)를 가리키게 한다.
새 노드를 이전 노드로 지정한다.
마지막 노드를 새 노드의 prev로 지정한다.
기존 마지막 노드의 next를 새 노드로 지정한다.
insert_pos() = 리스트의 지정한 위치에 요소를 삽입한다.
삽입할 데이터를 입력받는다.
요소를 삽입할 위치를 입력받는다.
리스트가 비어 있으면 첫 위치에 노드를 삽입한다.
리스트가 비어 있지 않으면 해당 위치의 노드와 그 다음 노드를 찾는다.
두 노드 사이에 새 노드를 삽입한다.
delete_pos() = 리스트의 지정한 위치에서 요소를 삭제한다.
리스트가 비어 있으면 종료한다.
삭제할 노드의 위치를 입력받는다.
노드가 하나뿐이면 삭제하고 next, prev 포인터를 갱신한다.
노드가 여러 개면 해당 위치의 노드를 삭제하고 next, prev 포인터를 갱신한다.
sort() = 리스트의 요소들을 정렬한다.
리스트가 비어 있으면 종료한다.
리스트의 요소들을 정렬한다.
display() = 리스트를 화면에 출력한다.
reverse() = 리스트를 역순으로 뒤집는다.
끝예제 코드
아래 C++ 프로그램은 메뉴 기반으로 동작하며, 맨 앞 삽입, 맨 뒤 삽입, 특정 위치 삽입, 특정 위치 삭제, 정렬, 출력, 역순 변환 기능을 모두 제공합니다.
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct nod {
int info;
struct nod *n;
struct nod *p;
}*start, *last;
int count = 0;
class circulardoublylist {
public:
nod *create_node(int);
void insert_begin();
void insert_end();
void insert_pos();
void delete_pos();
void sort();
void display();
void reverse();
circulardoublylist() {
start = NULL;
last = NULL;
}
};
int main() {
int c;
circulardoublylist cdl;
while (1) {
cout<<"1.Insert at Beginning"<<endl;
cout<<"2.Insert at End"<<endl;
cout<<"3.Insert at Position"<<endl;
cout<<"4.Delete at Position"<<endl;
cout<<"5.sort the list"<<endl;
cout<<"6.Display List"<<endl;
cout<<"7.Reverse List"<<endl;
cout<<"8.Exit"<<endl;
cout<<"Enter your choice : ";
cin>>c;
switch(c) {
case 1:
cdl.insert_begin();
break;
case 2:
cdl.insert_end();
break;
case 3:
cdl.insert_pos();
break;
case 4:
cdl.delete_pos();
break;
case 5:
cdl.sort();
break;
case 6:
cdl.display();
break;
case 7:
cdl.reverse();
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}
nod* circulardoublylist::create_node(int v) {
count++;
struct nod *t;
t = new(struct nod);
t->info = v;
t->n = NULL;
t->p = NULL;
return t;
}
void circulardoublylist::insert_begin() {
int v;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout<<"Element inserted in empty list"<<endl;
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
t->n = start;
start->p = t;
start = t;
start->p = last;
last->n = start;
cout<<"Element inserted"<<endl;
}
}
void circulardoublylist::insert_end() {
int v;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
struct nod *t;
t = create_node(v);
if (start == last && start == NULL) {
cout<<"Element inserted in empty list"<<endl;
start = last = t;
start->n= last->n = NULL;
start->p = last->p= NULL;
} else {
last->n= t;
t->p= last;
last = t;
start->p = last;
last->n= start;
}
}
void circulardoublylist::insert_pos() {
int v, pos, i;
cout<<endl<<"Enter the element to be inserted: ";
cin>>v;
cout<<endl<<"Enter the position of element inserted: ";
cin>>pos;
struct nod *t, *s, *ptr;
t = create_node(v);
if (start == last && start == NULL) {
if (pos == 1) {
start = last = t;
start->n = last->n = NULL;
start->p = last->p = NULL;
} else {
cout<<"Position out of range"<<endl;
count--;
return;
}
} else {
if (count < pos) {
cout<<"Position out of range"<<endl;
count--;
return;
}
s = start;
for (i = 1;i <= count;i++) {
ptr = s;
s = s->n;
if (i == pos - 1) {
ptr->n = t;
t->p= ptr;
t->n= s;
s->p = t;
cout<<"Element inserted"<<endl;
break;
}
}
}
}
void circulardoublylist::delete_pos() {
int pos, i;
nod *ptr, *s;
if (start == last && start == NULL) {
cout<<"List is empty, nothing to delete"<<endl;
return;
}
cout<<endl<<"Enter the position of element to be deleted: ";
cin>>pos;
if (count < pos) {
cout<<"Position out of range"<<endl;
return;
}
s = start;
if(pos == 1) {
count--;
last->n = s->n;
s->n->p = last;
start = s->n;
free(s);
cout<<"Element Deleted"<<endl;
return;
}
for (i = 0;i < pos - 1;i++ ) {
s = s->n;
ptr = s->p;
}
ptr->n = s->n;
s->n->p = ptr;
if (pos == count) {
last = ptr;
}
count--;
free(s);
cout<<"Element Deleted"<<endl;
}
void circulardoublylist::sort() {
struct nod *t, *s;
int v, i;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to sort"<<endl;
return;
}
s = start;
for (i = 0;i < count;i++) {
t= s->n;
while (t != start) {
if (s->info > t->info) {
v = s->info;
s->info = t->info;
t->info = v;
}
t = t->n;
}
s = s->n;
}
cout<<"List sorted"<<endl;
}
void circulardoublylist::display() {
int i;
struct nod *s;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to display"<<endl;
return;
}
s = start;
for (i = 0;i < count-1;i++) {
cout<<s->info<<"<->";
s = s->n;
}
cout<<s->info<<endl;
}
void circulardoublylist::reverse() {
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to reverse"<<endl;
return;
}
struct nod *p1, *p2;
p1 = start;
p2 = p1->n;
p1->n = NULL;
p1->p= p2;
while (p2 != start) {
p2->p = p2->n;
p2->n = p1;
p1 = p2;
p2 = p2->p;
}
last = start;
start = p1;
cout<<"List Reversed"<<endl;
}실행 결과
프로그램을 실행하면 메뉴가 반복해서 표시되고, 사용자가 선택한 번호에 따라 각 기능이 수행됩니다. 아래는 실제 실행 예시입니다.
1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.sort the list 6.Display List 7.Reverse List 8.Exit Enter your choice : 1 Enter the element to be inserted: 7 Element inserted in empty list ... Enter your choice : 6 6<->7<->4<->5 ... Enter your choice : 5 List sorted ... Enter your choice : 4 Enter the position of element to be deleted: 3 Element Deleted ... Enter your choice : 6 4<->5<->7 ... Enter your choice : 7 List Reversed ... Enter your choice : 6 7<->5<->4 ... Enter your choice : 8
정리
이 예제는 순환 이중 연결 리스트의 핵심 연산인 삽입, 삭제, 정렬, 출력, 역순 변환을 모두 다룹니다. 특히 sort() 함수는 노드의 데이터 값을 서로 교환하는 방식으로 리스트를 오름차순으로 정렬하며, reverse() 함수는 각 노드의 next와 prev 포인터를 뒤바꿔 리스트 전체의 방향을 반전시킵니다. 순환 구조의 특성상 마지막 노드와 첫 번째 노드가 항상 서로 연결되어 있으므로, 포인터 갱신 시 시작 노드(start)와 마지막 노드(last)를 함께 관리하는 것이 중요합니다.