C++ 이중 연결 리스트 구현 — 더미 Head·Tail과 삽입·삭제

C++ 이중 연결 리스트는 각 노드가 이전 노드와 다음 노드를 모두 가리키는 자료구조다. 이 글에서는 값이 없는 더미 Head와 Tail을 두어 빈 리스트와 양 끝 삽입·삭제에서 필요한 연결 처리를 단순하게 만드는 방법을 구현한다.
핵심 구조
삽입할 때는 새 노드의 prev와 next, 양쪽 이웃 노드의 next와 prev까지 네 연결을 맞춘다.삭제할 때는 삭제할 노드의 앞뒤 노드를 서로 연결한 다음 메모리를 해제한다.더미 Head와 Tail은 실제 데이터를 저장하지 않고 리스트의 경계 역할만 한다.
연산별 시간 복잡도
연산시간 복잡도맨 앞·맨 뒤 삽입/삭제O(1)위치를 알고 있는 노드의 삽입/삭제O(1)인덱스 탐색O(N)
구현할 때 주의할 점
아래 예제의 삭제 함수는 리스트에 원소가 있다고 가정한다. 실제로 사용할 때는 size가 0이면 삭제하지 않는 검사가 필요하다. 또한 예제의 소멸자는 비어 있으므로, 완성된 구현에서는 남은 모든 데이터 노드와 더미 Head·Tail을 순회하며 delete해 메모리 누수를 막아야 한다. FindByIndex에도 범위를 벗어난 인덱스를 별도로 처리하는 편이 안전하다.



1. 이중 연결 리스트란?
이중 연결 리스트란 단일 연결리스트와 다르게 양방향으로 노드가 이어진 리스트이다.  이중 연결 리스트는 이전 노드와 이후 노드가 이어져 있기 때문에 삽입 삭제 연산 시 이전, 이후 노드를 저장하지 않아도 되기 때문에 훨씬 유연하게 사용할 수 있다.


2. 이중 연결 리스트 구현
이번 이중 연결 리스트 구현은 Head와 Tail에 data가 들어있지 않은 더미(dummy)노드를 사용해서 구현했다.
2-1. 구조체 및 클래스 선언부
이중 연결 리스트는 노드 두개가 서로 연결 되어있기 때문에 이전 노드와 다음 노드를 포인팅하는 prev, next 구조체 포인터를 선언해줬다.
이중 연결 리스트의 노드
struct Node { Node* prev; Node* next; int data; }; class DoublyLinkedList{ private: Node* head; Node* tail; int size = 0; public: DoublyLinkedList(); ~DoublyLinkedList() {} void AddHead(int value); void AddTail(int value); void AddSomewhere(Node* node, int value); void DeleteHead(); void DeleteTail(); void DeleteSomewhere(Node* node); Node* FindByIndex(int idx); void PrintAll(); };
2-2. FindByIndex
원하는 인덱스에 값을 삽입하기 위해 인덱스로 노드를 찾는 함수이다. 인덱스를 매개변수로 받아서 찾은 노드를 반환한다.
Node* DoublyLinkedList::FindByIndex(int idx) { if(idx < 0 || idx > size) return tail; Node* temp = head->next; for(int i = 0; i < idx-1; i++) { temp = temp->next; } return temp; }
2-3. AddHead
리스트의 맨 앞 Head부분에 삽입하는 함수이다.
void DoublyLinkedList::AddHead(int value) { Node* newNode = new Node; newNode->data = value; //0 newNode->next = head->next; //1 head->next = newNode; //2 newNode->prev = newNode->next->prev; //3 newNode->next->prev = newNode; //4 size++; }
0. 삽입할 데이터를 담은 노드를 생성한다.1. 새로운 노드의 next를 head의 next로 포인팅한다. (첫번째 원소 삽입 연산이면 tail을 포인팅한다.)2. head의 next는 새로운 노드를 포인팅한다.3. 새로운 노드가 포인팅하는 이전노드는 새로운 노드의 다음 노드의 이전노드를 포인팅한다.(첫번째 원소 삽입 연산이면 Head노드를 포인팅 함)4. 새 노드의 다음 노드가 가리키는 prev를 새 노드로 변경한다.
말로만 하면 어렵기 때문에 아래 그림을 보자

2-4. AddTail
Tail에 원소를 삽입하는 함수이다.
void DoublyLinkedList::AddTail(int value) { Node* newNode = new Node; newNode->data = value; newNode->prev = tail->prev; //1 tail->prev = newNode; //2 newNode->next = newNode->prev->next; //3 newNode->prev->next = newNode; //4 size++; }
2-5. AddSomewhere
내가 원하는 인덱스에 원소를 삽입하는 함수이다.
void DoublyLinkedList::AddSomewhere(Node* node, int value) { Node* newNode = new Node; newNode->data = value; newNode->next = node; //1 node->prev->next = newNode; //2 newNode->prev = node->prev; //3 node->prev = newNode; //4 size++; }
2-6. DeleteHead
Head쪽 즉 가장 앞에 있는 원소를 삭제하는 함수이다.
void DoublyLinkedList::DeleteHead() { head->next = head->next->next; //1 delete(head->next->prev); //2 head->next->prev = head; //3 size--; }
삭제 연산은 삽입연산보다 비교적 쉽다.
1. Head 노드가 포인팅 하는 노드를 삭제하고 싶은 노드의 다음 노드를 포인팅한다.
2. 삭제하고싶은 노드의 메모리를 해제해준다.(안하면 메모리 누수)
3. Head다음 노드가 포인팅하는 prev노드를 Head노드로 변경해준다.

삭제 연산 부분도 말로하면 어려우니 아래의 그림으로 보자

2-7. DeleteTail
Tail과 연결된 노드를 삭제하는 함수다.
void DoublyLinkedList::DeleteTail() { tail->prev = tail->prev->prev; delete(tail->prev->next); tail->prev->next = tail; size--; }
2-8. DeleteSomewhere
원하는 부분의 인덱스를 받아서 해당 노드를 삭제하는 연산이다.
void DoublyLinkedList::DeleteSomewhere(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; delete(node); size--; }
3. 전체 코드
#include <iostream> #include <cstdlib> using namespace std; struct Node { Node* prev; Node* next; int data; }; class DoublyLinkedList{ private: Node* head; Node* tail; int size = 0; public: DoublyLinkedList(); ~DoublyLinkedList() {} void AddHead(int value); void AddTail(int value); void AddSomewhere(Node* node, int value); void DeleteHead(); void DeleteTail(); void DeleteSomewhere(Node* node); Node* FindByIndex(int idx); void PrintAll(); }; DoublyLinkedList::DoublyLinkedList() { head = new Node; tail = new Node; head->next = tail; tail->prev = head; size = 0; } void DoublyLinkedList::AddHead(int value) { Node* newNode = new Node; newNode->data = value; newNode->next = head->next; head->next = newNode; newNode->prev = newNode->next->prev; newNode->next->prev = newNode; size++; } void DoublyLinkedList::AddTail(int value) { Node* newNode = new Node; newNode->data = value; newNode->prev = tail->prev; tail->prev = newNode; newNode->next = newNode->prev->next; newNode->prev->next = newNode; size++; } void DoublyLinkedList::AddSomewhere(Node* node, int value) { Node* newNode = new Node; newNode->data = value; newNode->next = node; node->prev->next = newNode; newNode->prev = node->prev; node->prev = newNode; size++; } void DoublyLinkedList::DeleteHead() { head->next = head->next->next; delete(head->next->prev); head->next->prev = head; size--; } void DoublyLinkedList::DeleteTail() { tail->prev = tail->prev->prev; delete(tail->prev->next); tail->prev->next = tail; size--; } void DoublyLinkedList::DeleteSomewhere(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; delete(node); size--; } Node* DoublyLinkedList::FindByIndex(int idx) { if(idx < 0 || idx > size) return tail; Node* temp = head->next; for(int i = 0; i < idx-1; i++) { temp = temp->next; } return temp; } void DoublyLinkedList::PrintAll() { cout << "Head"; Node* node = head->next; while(node != tail) { cout << " - " << node->data; node = node->next; } cout << " - Tail" << "\n"; } void menuPrint() { cout << "==============DoublyLinkedList===============" << "\n"; cout << "[1] AddHead" << "\n"; cout << "[2] AddTail" << "\n"; cout << "[3] AddSomewhere" << "\n"; cout << "[4] DeleteHead" << "\n"; cout << "[5] DeleteTail" << "\n"; cout << "[6] DeleteSomewhere" << "\n"; cout << "[7] PrintAll" << "\n"; cout << "[Exit] Exit(1~6제외 아무키나 누르세요)" << "\n"; } int main() { DoublyLinkedList DLL; while(true) { menuPrint(); char cmd; cin >> cmd; if(cmd == '1') { int value; cout << "제일 처음에 삽입 할 값 입력 : "; cin >> value; DLL.AddHead(value); } else if(cmd == '2') { int value; cout << "제일 끝에 삽입 할 값 입력 : "; cin >> value; DLL.AddTail(value); } else if(cmd == '3') { int value, idx; cout << "원하는 인덱스 : " ; cin >> idx; cout << "\n"; cout << "삽입 할 값 입력 : "; cin >> value; DLL.AddSomewhere(DLL.FindByIndex(idx), value); } else if(cmd == '4') { DLL.DeleteHead(); } else if(cmd == '5') { DLL.DeleteTail(); } else if(cmd == '6') { int idx; cout << "삭제를 원하는 인덱스 : " ; cin >> idx; DLL.DeleteSomewhere(DLL.FindByIndex(idx)); } else if(cmd == '7') { DLL.PrintAll(); } else { exit(0); } } }

백문이 불여일타 연결리스트는 확실히 그림 그려가면서 구현해보는게 훨씬 이해가 빠른 것 같다.
CS 지식을 공부하고 기록하는 개인 공부 블로그입니다.내용 중 틀린 부분 피드백 혹은 궁금한 점이 있으면 댓글로 남겨주시면 참고 및 답변 달아드리겠습니다🧐