■ 양방향 연결 리스트
양방향 연결 리스트는 하나의 노드가 자신의 왼쪽(이전)과 오른쪽(다음) 노드를 동시에 가리키는 구조이다.
- 양방향 리스트이면서, 원형 연결 리스트를 동시에 지니는 리스트도 존재한다.
그림만 보면 양방향 리스트의 구현은 어려워 보이지만, 양쪽 방향으로 이동할 수 있기 때문에 단방향에서 어렵게 구현했던 것이 쉽게 구현되기도 한다.
양방향 리스트 역시 끝을 가리키는 Tail노드를 사용하지 않고 데이터를 맨 앞에 추가하는 방식으로 구현해 보겠다.
■ 추상 자료형 정의
#pragma once
typedef int LData;
struct Node
{
LData data;
Node* prev = nullptr;
Node* next = nullptr;
};
struct DoublyLinkedList
{
Node* head = nullptr;
Node* cur = nullptr;
int count = 0;
};
typedef DoublyLinkedList List;
void InitList(List* p_list);
void Add(List* p_list, LData data);
bool First(List* p_list, LData* data);
bool Next(List* p_list, LData* data);
LData Remove(List* p_list);
LData RemoveAt(List* p_list, int index);
int Count(List* p_list);
bool CheckListNull(List* p_list);
| 정의 | 기능 |
| void InitList(List* pList) | 초기화 할 리스트의 주소 값을 전달. 리스트 생성 후 가장 먼저 호출. |
| void Add(List* pList, LData data): | 리스트에 데이터를 저장. |
| bool First(List* pList, LData* data) | 리스트의 첫 번째 데이터를 data가 가리키는 메모리에 저장.→참조 여부에 따라 bool 값 반환. |
| bool Next(List* pList, LData* data) | 참조된 데이터의 다음 데이터가 data가 가리키는 메모리에 저장.→참조 여부에 따라 bool 값 반환. |
| LData Remove(List* pList) | First, Next의 마지막 반환 데이터를 삭제 후 반환. |
| LData RemoveAt(List* p_list, int index); | 특정 index위치에 저장된 값 삭제 |
| int Count(List* pList) | 리스트에 저장된 데이터 수 반환. |
[DoublyLinkedList.h]
양방향 리스트의 추상 자료형도 단방향 리스트와 동일하다.
struct Node
{
LData data;
Node* nextNode = nullptr;
};
struct LinkedList
{
Node* head = nullptr;
Node* cur = nullptr;
Node* prev = nullptr;
int count = 0;
};
struct Node
{
LData data;
Node* prev = nullptr;
Node* next = nullptr;
};
struct DoublyLinkedList
{
Node* head = nullptr;
Node* cur = nullptr;
int count = 0;
};
[단방향 리스트의 노드 구조체(위)와 양방향 리스트의 노드 구조체(아래)]
단방향 리스트는 노드가 next포인터만 가지고 있기 때문에, 특정 노드를 삭제하거나 이전 노드를 추적하기가 어렵다.
- 따라서 LinkedList구조체 내부에 prev 포인터를 별도로 저장.
하지만 양방향 리스트는 각 노드 자체가 이전 노드 포인터(prev)를 포함하고 있기 때문에, 리스트 구조체에서 별도의 prev 변수는 필요 없다.
■ 기능 구현(DoublyLinkedList.cpp)
1. 초기화 및 삽입(InitList, Add)
void InitList(List* p_list)
{
if(p_list == nullptr)
return;
// Head가 존재하지 않는 경우
if(p_list->head == nullptr)
{
auto newNode = new Node();
p_list->head = newNode;
p_list->cur = newNode;
p_list->count = 0;
return;
}
// Head와 데이터가 존재하는 경우
auto iter = p_list->head->next;
while(iter != nullptr)
{
auto del = iter;
iter = iter->next;
delete del;
}
// Head만 존재하는 경우
p_list->head->next = nullptr;
p_list->cur = p_list->head;
p_list->count = 0;
}
리스트를 초기화하는 함수이다. 리스트에 Head가 존재하지 않으면 첫 노드를 가리키는 Head노드를 할당한다.
리스트에 데이터가 존재하는 상태에서 새로운 Head를 할당하면, 기존에 저장된 데이터는 더 이상 접근이 불가능하다.
- 따라서 모든 데이터를 해제한 뒤, Head노드를 재할당 하지 않고 초기화하는 방식으로 구현하였다.
// push_front
void Add(List* p_list, LData data)
{
if(CheckListNull(p_list) == true)
return;
auto newNode = new Node();
newNode->data = data;
auto oldFirst = p_list->head->next;
// 새 노드를 연결
newNode->prev = p_list->head;
newNode->next = oldFirst;
// 기존 노드 연결
p_list->head->next = newNode;
if (oldFirst != nullptr)
{
oldFirst->prev = newNode;
}
p_list->count++;
}
bool CheckListNull(List* p_list)
{
if (p_list == nullptr || p_list->head == nullptr)
{
cout << "List is not initialized Or Empty." << endl;
return true;
}
return false;
}
단방향 리스트는 새 노드를 추가할 때 다음(next) 방향만 고려하면 되지만, 양방향 리스트는 이전(prev) 방향도 함께 연결해야 한다.
| 포인터 | Head노드 | 추가할 노드(newNode) | 기존 첫 번째 노드(oldFirst) |
| prev | nullptr(변경 없음) | head | newNode |
| next | newNode | oldFirst | 변경 없음 |
- 새 노드의 prev를 head로 설정한다.
- 새 노드의 next를 기존 첫 노드(head→next)로 설정한다.
- head→next를 새 노드로 변경하여 연결한다.
- 기존 첫 노드(oldFirst)가 존재한다면(nullptr이 아닐 경우), 그 노드의 prev를 새 노드와 연결한다.
이처럼 양방향 리스트는 노드를 추가할 때 앞 방향뿐 아니라 뒤 방향도 함께 갱신해야 하므로, 포인터의 연결 순서와 null체크가 매우 중요하다.
- 하지만 이전 노드로의 접근이 가능하니, 삭제나 역방향 탐색에서 큰 장점을 가진다.
2. 탐색 함수(First, Next)
bool First(List* p_list, LData* data)
{
if (CheckListNull(p_list) == true || p_list->head->next == nullptr)
return false;
p_list->cur = p_list->head->next;
*data = p_list->cur->data;
return true;
}
bool Next(List* p_list, LData* data)
{
if(CheckListNull(p_list) == true ||
p_list->cur->next == nullptr)
return false;
p_list->cur = p_list->cur->next;
*data = p_list->cur->data;
return true;
}
- First는 현재 참조 위치(cur)를 첫 번째 데이터가 저장된 위치로 이동하고 첫 번째 저장된 데이터를 반환한다.
- Next()는 현재 참조 위치를 다음 노드로 이동시킨다.
2. 삭제 함수(Remove, RemoveAt)
LData Remove(List* p_list)
{
if(CheckListNull(p_list) == true || p_list->cur == nullptr)
{
return -1;
}
auto delNode = p_list->cur; // 삭제할 노드
auto prev = delNode->prev; // 삭제 노드의 이전 노드(최소 Head)
auto next = delNode->next; // 삭제 노드의 다음 노드(최대 nullptr)
// 다음 노드로 이동 가능하면
if(next != nullptr)
{
p_list->cur = next;
}
// 이전 노드로 이동하고, 이전 노드가 head가 아니라면
else if(prev != nullptr && prev != p_list->head)
{
p_list->cur = prev;
}
// cur가 이동이 불가능한 경우(더 이상 남은 노드 없음)
else
{
p_list->cur = nullptr;
}
if (prev != nullptr) prev->next = next;
if (next != nullptr) next->prev = prev;
LData result = delNode->data;
delete delNode;
p_list->count--;
return result;
}
단방향 리스트에서 노드를 삭제할 때, 이전 참조 위치(prev)를 갱신하지 못해 연속적인 Remove() 함수 호출이 불가능했다.
양방향에선 노드가 이전 노드의 정보를 가지고 있으므로, 현재 참조 위치(cur)만 알맞게 갱신해 주어 연속적인 삭제가 가능하도록 구현하였다.
노드를 삭제할 때는 다음과 같은 순서를 따른다.
- 삭제할 노드의 이전 노드(prev)와 다음 노드(next)의 포인터 저장.
- prev→next = next; 를 수행하여 앞 노드를 다음 노드와 연결한다.
- next→prev = prev; 를 수행하여 뒤 노드를 이전 노드와 연결한다.
- 삭제할 노드 할당 해제.
여기서 중요한 점은 연속적인 Remove함수 호출을 위해 현재 참조 위치(cur)를 갱신해줘야 한다.
삭제할 노드의 다음 노드가 존재하는 경우. if(next != nullptr)
cur를 오른쪽(다음 노드)으로 이동하여 순방향 삭제를 계속할 수 있다.
다음 노드가 없고, 이전 노드가 Head가 아닌 경우. else if(prev != nullptr && prev != p_list->head)
리스트의 끝까지 삭제된 상태이므로, cur을 왼쪽(이전 노드)으로 이동시켜 삭제를 이어간다.
- 단, head는 데이터가 아니므로 cur가 head를 가리키지 않도록 조건을 설정한다.
모든 노드가 삭제된 경우.
리스트가 완전히 비어 있으므로, cur를 nullptr로 설정하여 더 이상 삭제가 불가능하게 한다.
단방향 리스트에서는 삭제 시 이전 노드를 추적하기 위해 추가적인 변수나 연산이 필요하지만, 양방향 리스트는 노드 자체에 prev 포인터를 포함하고 있기 때문에 구조적으로 연속 삭제에 최적화되어 있다.
■ 실행 결과와 링크드 리스트의 단점
#include<iostream>
#include<random>
#include "DoublyLinkedList.h"
using namespace std;
int main()
{
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<int> dist(1, 100);
List list;
InitList(&list);
for(int i = 0; i < 10; i++)
{
Add(&list, dist(gen));
}
// 저장된 데이터 값 확인
LData data;
if(First(&list, &data) == true)
{
cout << data << ", ";
while(Next(&list, &data) == true)
{
cout << data << ", ";
}
cout << endl << "저장된 데이터 개수 : " << Count(&list) << endl << endl;
}
// 첫 번째 데이터 삭제
First(&list, &data);
Remove(&list);
Remove(&list);
if (First(&list, &data) == true)
{
cout << data << ", ";
while (Next(&list, &data) == true)
{
cout << data << ", ";
}
cout << endl << "저장된 데이터 개수 : " << Count(&list) << endl << endl;
}
// 특정 위치 삭제 확인
RemoveAt(&list, 8);
if (First(&list, &data) == true)
{
cout << data << ", ";
while (Next(&list, &data) == true)
{
cout << data << ", ";
}
cout << endl << "저장된 데이터 개수 : " << Count(&list) << endl << endl;
}
return 0;
}
링크드 리스트는 크기가 동적으로 늘어나며, 노드 삽입/삭제 시 주변 노드의 포인터만 변경하면 되기 때문에 매우 유용해 보인다.
하지만 연결 리스트에는 매우 큰 단점이 존재한다.
😪 인덱스로 직접 접근할 수 없다!
array[5] // = 시작 주소 + (인덱스 * 자료형 크기)
배열은 메모리가 연속된 형태로 배치되어 있기 때문에, 위와 같이 단 한 번의 연산으로 원하는 위치에 즉시 접근$(O(1))$할 수 있다.
head -> node1 -> node2 -> node3 -> ...
반면 링크드 리스트는 노드가 메모리에 흩어져 분산되어 저장되어 있고, 각 노드는 오직 다음 노드의 주소만 알고 있기 때문에 원하는 위치에 도달하려면 head부터 차례대로$(O(n))$ 따라가야 하므로, 인덱서를 사용할 수 없다.
즉, 링크드 리스트는 “특정 위치에 빠르게 접근”하는 용도로는 적합하지 않다. 인덱스를 통한 랜덤 접근이 불가능하기 때문에 배열 또는 배열 기반 리스트가 더 효율적인 경우가 많다.
| 언어/자료구조 이름 | 내부 구현 방식 | 특징 |
| C++ STL의 std::list | 양방향 연결 리스트 (Doubly Linked List) | 노드 기반, 삽입/삭제 O(1), 인덱스 접근 불가 |
| C++ STL의 std::vector | 배열 기반 동적 배열 | C#의 List와 유사 |
| C#의 List<T> | 동적 배열 기반 | 인덱스 접근 O(1), 삽입/삭제는 위치에 따라 O(n) |
| C#의 LinkedList<T> | 양방향 연결 리스트 | C++ std::list와 유사한 구조 |
이러한 링크드 리스트의 특성 때문에 C#의 List, C++의 vector는 동적 배열 기반으로 설계되었다.
즉, 모든 List가 LinkedList를 의미하는 것이 아니며 List는 것은 추상 자료형(ADT)에 해당할 뿐, 내부 구현 방식은 배열일 수도 있고 연결 리스트일 수도 있다.
'C++ > 자료구조' 카테고리의 다른 글
| [C++, 자료구조] stack의 응용 : 계산기 프로그램 (0) | 2025.11.11 |
|---|---|
| [C++, 자료구조] 스택(Stack) (1) | 2025.11.11 |
| [C++, 자료구조] 단일 연결 리스트(Singly Linked List) (0) | 2025.10.23 |
| [C++, 자료구조] 순차 리스트(ArrayList)와 추상 자료형 (0) | 2025.10.23 |