이중 연결 리스트란 무엇인가?
이중 연결 리스트(Doubly Linked List)는 자기 참조 구조체(self-referential structure)를 사용해 생성한 노드들로 구성되는 대표적인 자료구조입니다. 각 노드는 세 가지 요소로 이루어져 있는데, 바로 데이터(data), 다음 노드를 가리키는 포인터(next), 그리고 이전 노드를 가리키는 포인터(prev)입니다.
전체 연결 리스트에 접근하려면 첫 번째 노드에 대한 참조만 있으면 충분하며, 이를 헤드(head)라고 합니다. 리스트의 마지막 노드는 더 이상 가리킬 다음 노드가 없으므로 해당 위치에 NULL을 저장합니다. 또한 각 노드가 이전 노드와 다음 노드를 모두 가리키고 있기 때문에, 이중 연결 리스트는 단일 연결 리스트와 달리 양방향 순회가 가능하다는 큰 장점이 있습니다.
그럼 C++로 이중 연결 리스트를 구현하는 전체 프로그램을 살펴보겠습니다.
C++ 구현 예제
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* head = NULL;
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode;
head = newnode;
}
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}실행 결과
The doubly linked list is: 9 2 7 1 3
코드 상세 설명
1. Node 구조체 정의
위 프로그램에서 Node 구조체가 이중 연결 리스트의 노드 역할을 담당합니다. 이 구조체는 정수형 데이터와 함께 이전 노드 및 다음 노드를 가리키는 두 개의 포인터를 멤버로 가집니다.
struct Node {
int data;
struct Node *prev;
struct Node *next;
};2. insert() 함수 — 노드 삽입
insert() 함수는 새로운 데이터를 이중 연결 리스트의 맨 앞에 삽입하는 역할을 합니다. 먼저 새 노드(newnode)를 생성하고, 전달받은 값을 데이터 필드에 저장합니다. 새 노드는 리스트의 시작 부분에 추가되므로 prev 포인터는 NULL을 가리키고, next 포인터는 기존의 head를 가리킵니다. 만약 head가 NULL이 아니라면, 즉 기존 노드가 존재한다면 기존 head의 prev 포인터가 새 노드를 가리키도록 설정합니다. 마지막으로 head를 새 노드로 갱신하여 리스트의 시작점을 변경합니다.
void insert(int newdata) {
struct Node* newnode = (struct Node*) malloc(sizeof(struct Node));
newnode->data = newdata;
newnode->prev = NULL;
newnode->next = head;
if(head != NULL)
head->prev = newnode;
head = newnode;
}3. display() 함수 — 리스트 출력
display() 함수는 이중 연결 리스트 전체를 화면에 출력합니다. 우선 포인터 ptr이 head를 가리키도록 초기화한 뒤, ptr이 NULL이 될 때까지 계속해서 다음 노드로 이동하면서 각 노드의 데이터 값을 순서대로 출력합니다.
void display() {
struct Node* ptr;
ptr = head;
while(ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}4. main() 함수 — 프로그램 실행 흐름
main() 함수에서는 insert() 함수를 여러 번 호출해 이중 연결 리스트에 값들을 차례로 삽입한 후, display() 함수를 호출하여 전체 리스트를 출력합니다. 삽입이 항상 맨 앞에서 이루어지므로 마지막에 삽입된 9가 가장 먼저 출력되는 것을 확인할 수 있습니다.
int main() {
insert(3);
insert(1);
insert(7);
insert(2);
insert(9);
cout<<"The doubly linked list is: ";
display();
return 0;
}마무리 및 참고 사항
이처럼 이중 연결 리스트는 양방향 탐색이 가능해 삽입·삭제 작업이 유연하지만, 각 노드에 prev 포인터가 추가로 필요하므로 단일 연결 리스트보다 메모리를 더 많이 사용한다는 점을 기억해야 합니다. 또한 위 예제에서는 C 스타일의 malloc()을 사용했지만, C++에서는 new 연산자를 사용하는 것이 더 안전하고 관용적인 방법입니다.