자료구조에서 연결 리스트(Linked List)는 데이터 요소들을 선형으로 모아 놓은 집합입니다. 리스트의 각 요소, 즉 노드(node)는 두 가지 항목으로 구성됩니다. 하나는 실제 데이터이고, 다른 하나는 다음 노드를 가리키는 참조(reference)입니다. 마지막 노드의 참조는 null을 가리키며, 연결 리스트의 진입점(entry point)을 리스트의 헤드(head)라고 부릅니다.
단일 연결 리스트(singly linked list)에서 각 노드는 자신이 담고 있는 내용과 함께 리스트상 다음 노드를 가리키는 포인터 또는 참조를 저장합니다. 반면, 이전 노드에 대한 포인터나 참조는 저장하지 않습니다.
이번 글에서는 삽입될 때마다 정렬 상태가 유지되는 단일 연결 리스트를 C++로 구현하는 방법을 알아보겠습니다.
알고리즘
createnode() 함수 — 리스트에 노드 삽입
먼저 리스트가 비어 있는지 확인합니다. 리스트가 비어 있다면 새 노드를 첫 번째 요소로 넣고 head를 갱신한 뒤, next 포인터를 NULL로 초기화합니다.
리스트가 비어 있지 않다면 새 노드(newnode)를 생성하고 그 데이터 필드에 값을 저장합니다. 이때 새 노드는 연결 리스트가 항상 정렬된 상태를 유지하도록 알맞은 위치에 삽입됩니다. 리스트의 맨 끝에 삽입되는 경우 새 노드는 NULL을 가리키고, 맨 앞에 삽입되는 경우에는 연결 리스트가 해당 노드부터 시작하게 됩니다.
display() 함수 — n개의 노드를 가진 리스트 출력
카운터 c를 0으로 초기화하고, 포인터 변수를 시작 주소로 설정합니다. 그런 다음 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) {
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) {
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 = t->n;
c++;
}
}
int main() {
int i = 0, n, a;
cout<<"enter the no of nodes\n";
cin>>n;
while (i < n) {
cout<<"\nenter value of node\n";
cin>>a;
createnode(a);
i++;
}
cout<<"sorted singly link list"<<endl;
display(n);
}동작 원리
createnode() 함수는 노드 개수에 따라 세 가지 경우로 나누어 처리합니다. 첫 번째 노드를 삽입할 때는 해당 노드가 곧 head가 됩니다. 두 번째 노드를 삽입할 때는 기존 노드와 값을 비교하여 앞쪽에 넣을지 뒤쪽에 넣을지 결정합니다. 세 번째 노드부터는 head부터 순회하면서 새 값보다 큰 값을 가진 노드를 찾아 그 앞에 삽입합니다. 만약 끝까지 더 작은 값이 없다면 리스트의 마지막에 연결합니다.
정렬된 위치를 찾기 위해 리스트를 처음부터 순회해야 하므로, 노드 한 개를 삽입하는 데 걸리는 시간 복잡도는 O(n)입니다.
실행 결과
enter the no of nodes 5 enter value of node 6 enter value of node 4 enter value of node 7 enter value of node 3 enter value of node 2 sorted singly link list 2 3 4 6 7 2