자료구조에서 연결 리스트(Linked List)는 데이터 요소들을 선형으로 모아 놓은 집합입니다. 리스트의 각 요소, 즉 노드(node)는 두 가지 항목으로 구성됩니다. 하나는 실제 데이터이고, 다른 하나는 다음 노드를 가리키는 참조(포인터)입니다. 마지막 노드의 참조값은 null이며, 연결 리스트의 진입점을 리스트의 헤드(head)라고 부릅니다.
이중 연결 리스트(Doubly Linked List)는 노드라고 불리는 레코드들이 순차적으로 연결된 구조로 이루어져 있습니다. 각 노드는 세 개의 필드를 포함합니다. 하나의 데이터 필드와 두 개의 링크 필드로, 링크 필드는 각각 이전 노드(previous)와 다음 노드(next)를 참조합니다.
정렬된 이중 연결 리스트(Sorted Doubly Linked List)의 경우, 데이터 필드의 값을 기준으로 리스트 전체가 항상 정렬된 상태로 유지됩니다. 새로운 노드가 삽입될 때마다 알맞은 위치를 찾아 배치하므로, 언제든지 정렬된 순서로 데이터를 탐색할 수 있다는 것이 큰 장점입니다.
알고리즘
시작
createnode() 함수 — 리스트에 노드 삽입:
새 노드(newnode)를 생성하고 데이터 필드에 입력받은 값을 저장한다.
리스트가 비어 있는지 검사한다.
비어 있다면 해당 노드를 첫 번째 요소로 설정하고 head를 갱신한다.
prev와 next 포인터는 모두 NULL로 초기화한다.
리스트가 비어 있지 않다면,
새 노드를 기존 연결 리스트에 정렬 상태가 유지되도록 삽입한다.
prev와 next 포인터를 그에 맞게 갱신한다.
끝
시작
display_head() 함수 — head부터 리스트 출력:
카운터 c를 0으로 초기화한다.
포인터 변수를 head 노드의 주소로 초기화한다.
while (c <= i)
노드 정보를 출력한다.
포인터 변수를 갱신한다.
c를 1 증가시킨다.
끝
시작
display_tail() 함수 — tail부터 리스트 출력:
카운터 m을 0으로 초기화한다.
포인터 변수를 tail 노드의 주소로 초기화한다.
while (m <= i)
노드 정보를 출력한다.
포인터 변수를 갱신한다.
m을 1 증가시킨다.
끝
예제 코드
#include<iostream>
using namespace std;
struct nod {
int d;
nod *n, *p;
}
*p = NULL, *head = NULL, *r = NULL, *np = NULL, *tail = NULL;
int c = 0;
void createnode(int n) {
np = new nod;
np->d = n;
np->n = NULL;
np->p = NULL;
if (c == 0) {
tail = np;
head = np;
p = head;
p->n = head;
p->p = head;
c++;
} else if (c == 1) {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
p->n = np;
np->p = p;
tail = p;
} else if (np->d > p->d) {
p->n = np;
np->p = p;
np->n= head;
p->p = np;
}
c++;
} else {
p = head;
r = p;
if (np->d < p->d) {
np->n = p;
p->p = np;
head = np;
do {
p = p->n;
}
while (p->n != r);
tail = p;
p->n = np;
np->p = p;
} else if (np->d > p->d) {
while (p->n != head && np->d > p->d) {
r = p;
p = p->n;
if (p->n == head && (p->d < np->d)) {
p->n = np;
np->p = p;
np->n = head;
tail = np;
head->p = np;
break;
} else if (np->d< p->d) {
r->n= np;
np->p = r;
np->n= p;
p->p= np;
if (p->n != head) {
do {
p = p->n;
}
while (p->n != head);
}
tail = p;
break;
}
}
}
}
}
void display_head(int i) {
nod *t = head;
int c = 0;
while (c <= i) {
cout<<t->d<<"\t";
t = t->n;
c++;
}
cout<<endl;
}
void display_tail(int i) {
nod *t = tail;
int m = 0;
while (m <= i) {
cout<<t->d<<"\t";
t = t->p;
m++;
}
cout<<endl;
}
int main() {
int i = 0, n, a, ch;
cout<<"enter the no of nodes\n";
cin>>n;
while (i < n) {
cout<<"\nenter value of node\n";
cin>>a;
createnode(a);
i++;
}
cout<<"\nsorting Doubly Linked List head first\n";
display_head(n);
cout<<"\nsorting Doubly Linked List tail first\n";
display_tail(n);
}
출력 결과
enter the no of nodes 5 enter value of node 7 enter value of node 4 enter value of node 6 enter value of node 2 enter value of node 1 sorting Doubly Linked List head first 1 2 4 6 7 1 sorting Doubly Linked List tail first 7 6 4 2 1 7
결과 해설
위 실행 결과에서 사용자가 7, 4, 6, 2, 1을 차례로 입력했지만, 출력은 1 2 4 6 7과 같이 오름차순으로 정렬된 것을 확인할 수 있습니다. 이는 createnode() 함수가 노드를 삽입할 때마다 적절한 위치를 찾아 정렬 상태를 유지하기 때문입니다.
또한 출력 끝에 첫 번째 값이 한 번 더 표시되는데, 이는 이 코드가 환형(circular) 구조로 동작하고, 출력 함수의 반복 조건이 c <= i(즉, 노드 수보다 한 번 더 반복)이기 때문입니다. head부터 순방향으로 출력한 결과와 tail부터 역방향으로 출력한 결과가 서로 대칭을 이루므로, 이중 연결 리스트의 양방향 순회 특성을 잘 보여줍니다.