자료구조에서 연결 리스트(Linked List)는 데이터 요소들의 선형 집합입니다. 리스트의 각 요소 즉 노드(node)는 두 가지 항목으로 구성되는데, 하나는 실제 저장되는 데이터이고 다른 하나는 다음 노드를 가리키는 참조(포인터)입니다. 마지막 노드는 null을 참조하며, 연결 리스트에서 진입점(entry point)은 리스트의 헤드(head)라고 합니다.
원형 이중 연결 리스트(Circular Doubly Linked List)는 인접한 두 요소가 prev 포인터와 next 포인터로 서로 연결되는 자료구조입니다. 특히 마지막 노드가 next 포인터로 첫 번째 노드를 가리키고, 첫 번째 노드도 prev 포인터로 마지막 노드를 가리키기 때문에 리스트 전체가 하나의 원처럼 순환하는 구조를 갖습니다.
알고리즘
아래 예제에서는 다음과 같은 멤버 함수들을 가진 circulardoublylist 클래스를 생성합니다.
1. create_node(int) — 노드 생성
노드를 위한 메모리를 동적으로 할당하고 초기화합니다.
2. insert_begin() — 맨 앞에 요소 삽입
- A) 리스트가 비어 있으면 노드를 삽입하고 next, prev 포인터를 NULL로 설정합니다.
- B) 리스트가 비어 있지 않으면 데이터를 삽입한 뒤 next, prev 포인터를 적절히 설정하고 갱신합니다.
3. insert_end() — 맨 뒤에 요소 삽입
- A) 리스트가 비어 있으면 원형 이중 리스트 형태로 노드를 생성합니다.
- B) 마지막 노드를 찾습니다.
- C) 노드를 동적으로 생성합니다.
- D) 시작 노드(start)를 새 노드의 next로 만듭니다.
- E) 새 노드를 기존 마지막 노드의 다음(next)으로 연결합니다.
- F) 새 노드의 prev를 기존 마지막 노드로 설정합니다.
- G) 기존 마지막 노드의 next를 새 노드로 갱신합니다.
4. insert_pos() — 지정한 위치에 요소 삽입
- A) 삽입할 데이터를 입력받습니다.
- B) 요소를 삽입할 위치를 입력받습니다.
- C) 리스트가 비어 있으면 첫 번째 위치에 노드를 삽입합니다.
- D) 리스트가 비어 있지 않으면 해당 위치의 노드와 그다음 노드를 찾습니다.
- E) 두 노드 사이에 새 노드를 삽입합니다.
5. delete_pos() — 지정한 위치의 요소 삭제
- A) 리스트가 비어 있으면 그대로 반환합니다.
- B) 삭제할 노드의 위치를 입력받습니다.
- C) 노드가 하나뿐이라면 해당 노드를 삭제하고 next, prev 포인터를 갱신합니다.
- D) 노드가 여러 개라면 해당 위치의 노드를 삭제하고 next, prev 포인터를 갱신합니다.
6. search() — 요소 검색
- A) 리스트가 비어 있으면 그대로 반환합니다.
- B) 검색할 값을 입력받습니다.
- C) 요소가 발견된 위치를 출력합니다.
- D) 요소를 찾지 못하면 "찾을 수 없음"을 출력합니다.
7. update() — 특정 노드의 값 갱신
- A) 리스트가 비어 있으면 그대로 반환합니다.
- B) 갱신할 노드의 위치를 입력받습니다.
- C) 새 값을 입력받습니다.
- D) 해당 노드의 값을 갱신합니다.
8. display() / reverse()
display()는 리스트 전체를 화면에 출력하고, reverse()는 리스트의 순서를 반대로 뒤집습니다.
예제 코드
#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 search();
void update();
void display();
void reverse();
circulardoublylist() {
start = NULL;
last = NULL;
}
};
int main() {
int c;
circulardoublylist cdl;
while (1) //perform switch operation {
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.Update Node"<<endl;
cout<<"6.Search Element"<<endl;
cout<<"7.Display List"<<endl;
cout<<"8.Reverse List"<<endl;
cout<<"9.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.update();
break;
case 6:
cdl.search();
break;
case 7:
cdl.display();
break;
case 8:
cdl.reverse();
break;
case 9:
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::update() {
int v, i, pos;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to update"<<endl;
return;
}
cout<<endl<<"Enter the position of node to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>v;
struct nod *s;
if (count < pos) {
cout<<"Position out of range"<<endl;
return;
}
s = start;
if (pos == 1) {
s->info = v;
cout<<"Node Updated"<<endl;
return;
}
for (i=0;i < pos - 1;i++) {
s = s->n;
}
s->info = v;
cout<<"Node Updated"<<endl;
}
void circulardoublylist::search() {
int pos = 0, v, i;
bool flag = false;
struct nod *s;
if (start == last && start == NULL) {
cout<<"The List is empty, nothing to search"<<endl;
return;
}
cout<<endl<<"Enter the value to be searched: ";
cin>>v;
s = start;
for (i = 0;i < count;i++) {
pos++;
if (s->info == v) {
cout<<"Element "<<v<<" found at position: "<<pos<<endl;
flag = true;
}
s = s->n;
}
if (!flag)
cout<<"Element not found in the list"<<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.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 1 Enter the element to be inserted: 7 Element inserted in empty list 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 1 Enter the element to be inserted: 6 Element inserted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 2 Enter the element to be inserted: 4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 2 Enter the element to be inserted: 5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 7 6<->7<->4<->5 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 6 Enter the value to be searched: 7 Element 7 found at position: 2 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 6 Enter the value to be searched: 2 Element not found in the list 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 4 Enter the position of element to be deleted: 4 Element Deleted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 3 Enter the element to be inserted: 5 Enter the position of element inserted: 2 Element inserted 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 7 6<->5<->7<->4 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 8 List Reversed 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 7 4<->7<->5<->6 1.Insert at Beginning 2.Insert at End 3.Insert at Position 4.Delete at Position 5.Update Node 6.Search Element 7.Display List 8.Reverse List 9.Exit Enter your choice : 9