C++로 자료구조 직접 구현하기: 연결 리스트·이진 탐색 트리·해시 테이블·스택·큐
이 글의 핵심
STL을 두고 자료구조를 직접 구현해 보는 이유는 포인터와 메모리 소유권을 손으로 다뤄 보며 내부 동작을 이해하기 위해서입니다. 구현 과정에서 흔히 생기는 메모리 누수, 해제 후 접근하는 댕글링 포인터, 연결을 잘못 이어 생기는 무한 루프를 짚고, 실무에서 직접 구현이 필요한 경우와 아닌 경우를 구분합니다.
연결 리스트 (Linked List)
std::vector가 이미 있는데 연결 리스트를 직접 구현하는 이유는, 두 자료구조가 서로 다른 트레이드오프를 갖는 근본적으로 다른 메모리 레이아웃을 쓰기 때문입니다 — 벡터는 원소들이 하나의 연속된 메모리 블록에 붙어 있어 캐시 지역성이 뛰어나지만 중간 삽입/삭제 시 뒤의 모든 원소를 이동해야 하는 반면, 연결 리스트는 각 노드가 힙 여기저기 흩어져 있어 캐시 성능은 떨어지지만 일단 노드의 위치를 알고 있다면 삽입/삭제가 포인터 몇 개만 바꾸는 O(1) 연산입니다. push_front가 O(1)인 이유(새 노드를 만들어 head만 갱신)와 push_back이 O(n)인 이유(끝까지 순회해야 함)를 비교해 보면, 이 구현이 “뒤쪽 삽입을 자주 하는” 용도에는 비효율적이라는 것을 알 수 있습니다 — 실무에서 양쪽 끝 삽입이 모두 잦다면 꼬리 포인터를 별도로 유지하거나(뒤에서 다룰 큐처럼), 애초에 이중 연결 리스트(std::list)를 쓰는 것이 더 적합합니다.
template <typename T>
class LinkedList {
private:
struct Node {
T data;
Node* next;
Node(T val) : data(val), next(nullptr) {}
};
Node* head;
int size;
public:
LinkedList() : head(nullptr), size(0) {}
~LinkedList() {
while (head) {
Node* temp = head;
head = head->next;
delete temp;
}
}
void push_front(T value) {
Node* newNode = new Node(value);
newNode->next = head;
head = newNode;
size++;
}
void push_back(T value) {
Node* newNode = new Node(value);
if (!head) {
head = newNode;
} else {
Node* curr = head;
while (curr->next) {
curr = curr->next;
}
curr->next = newNode;
}
size++;
}
bool remove(T value) {
if (!head) return false;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
size--;
return true;
}
Node* curr = head;
while (curr->next && curr->next->data != value) {
curr = curr->next;
}
if (curr->next) {
Node* temp = curr->next;
curr->next = curr->next->next;
delete temp;
size--;
return true;
}
return false;
}
void print() {
Node* curr = head;
while (curr) {
cout << curr->data << " -> ";
curr = curr->next;
}
cout << "null" << endl;
}
};이진 탐색 트리 (Binary Search Tree)
BST의 핵심 불변식은 “모든 노드에 대해, 왼쪽 서브트리의 모든 값은 그 노드보다 작고 오른쪽 서브트리의 모든 값은 그 노드보다 크다”는 것이며, insertHelper와 searchHelper가 매 단계마다 value를 현재 노드와 비교해 왼쪽 또는 오른쪽으로만 재귀하는 것이 바로 이 불변식을 이용해 탐색 범위를 매번 절반씩 줄여나가는 방식입니다. 이것이 평균 O(log n) 성능을 내는 이유이자, 동시에 “최악의 경우 O(n)“이라는 한계의 근원이기도 합니다 — 입력이 이미 정렬된 순서로 삽입되면(1, 2, 3, 4, 5…) 트리는 왼쪽이나 오른쪽으로만 계속 뻗어나가는 사실상의 연결 리스트가 되어, 균형이 전혀 잡히지 않은 채 탐색이 O(n)으로 저하됩니다. inorderHelper가 왼쪽-노드-오른쪽 순서로 재귀하면 항상 정렬된 순서로 값이 출력되는 것도 BST 불변식의 직접적인 결과이며, destroyTree가 자식을 먼저 재귀적으로 삭제한 뒤 자신을 삭제하는 후위 순회를 쓰는 것은 부모를 먼저 삭제하면 그 자식들에 대한 포인터를 잃어버려 메모리 누수가 발생하기 때문입니다.
template <typename T>
class BST {
private:
struct Node {
T data;
Node* left;
Node* right;
Node(T val) : data(val), left(nullptr), right(nullptr) {}
};
Node* root;
Node* insertHelper(Node* node, T value) {
if (!node) {
return new Node(value);
}
if (value < node->data) {
node->left = insertHelper(node->left, value);
} else if (value > node->data) {
node->right = insertHelper(node->right, value);
}
return node;
}
bool searchHelper(Node* node, T value) {
if (!node) return false;
if (node->data == value) return true;
if (value < node->data) {
return searchHelper(node->left, value);
} else {
return searchHelper(node->right, value);
}
}
void inorderHelper(Node* node) {
if (!node) return;
inorderHelper(node->left);
cout << node->data << " ";
inorderHelper(node->right);
}
void destroyTree(Node* node) {
if (!node) return;
destroyTree(node->left);
destroyTree(node->right);
delete node;
}
public:
BST() : root(nullptr) {}
~BST() {
destroyTree(root);
}
void insert(T value) {
root = insertHelper(root, value);
}
bool search(T value) {
return searchHelper(root, value);
}
void inorder() {
inorderHelper(root);
cout << endl;
}
};
int main() {
BST<int> tree;
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.inorder(); // 20 30 40 50 70
cout << tree.search(40) << endl; // 1
}재귀 구현에는 성능 말고도 스택 깊이라는 현실적인 한계가 있습니다. 정렬된 순서로 값 10만 개를 넣으면 트리 높이가 10만이 되고, insertHelper·destroyTree가 그만큼 깊이 재귀하면서 기본 스택(리눅스 8MB, Windows 1MB)을 넘어 세그멘테이션 오류로 죽습니다. 탐색이 느려지는 것보다 소멸자에서 프로그램이 죽는 쪽이 먼저 드러나는 경우가 많아서 원인을 찾기 어렵습니다. 입력 순서를 통제할 수 없다면 반복문으로 구현하거나, 균형 트리(std::map의 레드블랙 트리처럼 높이를 O(log n)으로 유지)를 쓰는 것이 근본 해결입니다. 아래 그래프의 재귀 DFS도 정점이 일렬로 이어진 큰 그래프에서 같은 문제를 겪으므로, 실전에서는 명시적 스택을 쓰는 반복 DFS가 더 안전합니다.
이 BST에는 삭제가 없는데, 직접 구현해 보면 가장 까다로운 연산이 삭제입니다. 자식이 없거나 하나인 노드는 부모의 포인터를 바꿔 주면 끝나지만, 자식이 둘인 노드는 오른쪽 서브트리의 최솟값(중위 후속자)을 찾아 값을 옮긴 뒤 그 후속자를 대신 지워야 BST 불변식이 유지됩니다. 이 과정에서 부모 포인터 갱신을 빠뜨리면 트리 일부가 통째로 사라지거나 해제된 노드를 가리키게 됩니다.
해시 테이블 (Hash Table)
이 구현은 “개방 주소법(open addressing)” 방식의 해시 테이블입니다 — 각 키를 hash(key)로 계산한 인덱스에 직접 저장을 시도하고, 그 자리가 이미 다른 키로 차 있으면(충돌) probe(index, i)로 다음 후보 자리를 찾아 나가는 “선형 탐사(linear probing)“를 씁니다. 이는 각 버킷이 연결 리스트를 갖는 “체이닝(chaining)” 방식과 대비되는 선택인데, 개방 주소법은 모든 데이터가 하나의 연속된 배열(table) 안에 있어 캐시 지역성이 좋지만, 테이블이 채워질수록 탐사 체인이 길어져 성능이 급격히 나빠진다는 단점이 있습니다. insert가 size >= capacity * 0.7일 때 rehash()를 트리거하는 것이 바로 이 문제에 대한 방어책입니다 — 부하율(load factor)이 70%를 넘기 전에 테이블 크기를 두 배로 늘려 재배치함으로써, 탐사 체인이 무한정 길어지는 것을 막고 평균 O(1) 성능을 유지합니다. get에서 i >= capacity일 때 탐색을 중단하는 안전장치도 중요한데, 이것이 없으면 키가 테이블에 없을 때 probe가 같은 자리들을 계속 순환하며 무한 루프에 빠질 수 있습니다.
template <typename K, typename V>
class HashTable {
private:
struct Entry {
K key;
V value;
bool occupied;
Entry() : occupied(false) {}
};
vector<Entry> table;
int capacity;
int size;
int hash(const K& key) {
return std::hash<K>{}(key) % capacity;
}
int probe(int index, int i) {
return (index + i) % capacity; // 선형 탐사
}
public:
HashTable(int cap = 10) : capacity(cap), size(0) {
table.resize(capacity);
}
void insert(const K& key, const V& value) {
if (size >= capacity * 0.7) {
rehash();
}
int index = hash(key);
int i = 0;
while (table[probe(index, i)].occupied) {
if (table[probe(index, i)].key == key) {
table[probe(index, i)].value = value;
return;
}
i++;
}
int finalIndex = probe(index, i);
table[finalIndex].key = key;
table[finalIndex].value = value;
table[finalIndex].occupied = true;
size++;
}
bool get(const K& key, V& value) {
int index = hash(key);
int i = 0;
while (table[probe(index, i)].occupied) {
if (table[probe(index, i)].key == key) {
value = table[probe(index, i)].value;
return true;
}
i++;
if (i >= capacity) break;
}
return false;
}
void rehash() {
vector<Entry> oldTable = table;
capacity *= 2;
table.clear();
table.resize(capacity);
size = 0;
for (const auto& entry : oldTable) {
if (entry.occupied) {
insert(entry.key, entry.value);
}
}
}
void print() {
for (int i = 0; i < capacity; i++) {
if (table[i].occupied) {
cout << "[" << i << "] " << table[i].key
<< " -> " << table[i].value << endl;
}
}
}
};개방 주소법에서 삭제를 추가하려면 주의해야 합니다. 삭제할 칸의 occupied를 그냥 false로 바꾸면, 그 칸을 지나 뒤쪽에 저장된 키들을 get이 찾지 못하게 됩니다. 탐사는 빈 칸을 만나면 “이 키는 없다”고 판단하고 멈추기 때문입니다. 그래서 삭제된 칸은 비어 있는 칸과 구분되는 묘비(tombstone) 로 표시해, 탐색은 계속 지나가고 삽입은 재사용하게 만들어야 합니다. 묘비가 쌓이면 탐사 체인이 다시 길어지므로 묘비 수까지 포함해 부하율을 계산하고 주기적으로 재해시해야 합니다.
해시 함수 선택도 성능을 좌우합니다. libstdc++의 std::hash<int>는 값을 그대로 돌려주는 항등 함수라서, 0, 10, 20, 30처럼 용량의 배수인 키를 넣으면 전부 같은 인덱스로 몰립니다. 선형 탐사는 이렇게 붙어 있는 칸들이 덩어리(primary clustering)를 이루며 성능이 빠르게 나빠지므로, 실무 구현은 용량을 2의 거듭제곱으로 두고 해시 값을 한 번 더 섞거나(예: 곱셈 해싱), 소수 크기 테이블을 씁니다. 표준 std::unordered_map이 체이닝을 쓰는 것도 반복자·참조 안정성 요구 사항 때문이며, 성능이 중요하면 개방 주소법 기반의 서드파티 해시 맵이 선택지가 됩니다.
스택 (Stack)
스택을 앞의 연결 리스트나 트리처럼 직접 노드와 포인터로 구현하지 않고 vector<T>로 감싼 것은 의도적인 선택입니다 — 스택이 요구하는 연산(끝에 추가, 끝에서 제거, 끝을 조회)은 정확히 vector가 O(1) 상각 시간에 가장 잘하는 연산과 일치하므로, 포인터를 직접 관리하는 연결 리스트 기반 구현보다 캐시 지역성이 좋고 코드도 훨씬 단순합니다. 이것이 실제 표준 라이브러리의 std::stack이 기본적으로 std::deque를 내부 컨테이너로 감싸는 “컨테이너 어댑터”로 설계된 이유와 정확히 같은 논리입니다 — 스택이라는 개념 자체는 밑바닥부터 새로 구현해야 할 자료구조가 아니라, 이미 존재하는 시퀀스 컨테이너의 인터페이스를 제한해서 얻는 뷰에 가깝습니다.
template <typename T>
class Stack {
private:
vector<T> data;
public:
void push(T value) {
data.push_back(value);
}
void pop() {
if (!empty()) {
data.pop_back();
}
}
T top() {
return data.back(); // 비어 있을 때 호출하면 정의되지 않은 동작 (std::stack과 동일)
}
bool empty() {
return data.empty();
}
int size() {
return data.size();
}
};큐 (Queue)
큐가 스택과 달리 연결 리스트로 구현된 이유는 큐의 연산 패턴이 앞서 다룬 “연결 리스트가 유리한 경우”에 정확히 해당하기 때문입니다 — 큐는 한쪽 끝(rear)에서 추가하고 반대쪽 끝(front)에서 제거해야 하는데, vector로 이를 구현하면 front 쪽 제거가 나머지 모든 원소를 앞으로 당겨야 하는 O(n) 연산이 됩니다. front와 rear 두 포인터를 모두 유지하면 양쪽 끝에서의 삽입/삭제가 각각 O(1)로 해결되며, dequeue에서 front가 nullptr이 될 때(마지막 원소를 제거한 경우) rear도 함께 nullptr로 되돌리는 처리를 빠뜨리기 쉬운데, 이를 놓치면 큐가 비어 있는데도 rear가 이미 삭제된 노드를 가리키는 댕글링 포인터로 남아 다음 enqueue에서 크래시로 이어집니다.
template <typename T>
class Queue {
private:
struct Node {
T data;
Node* next;
Node(T val) : data(val), next(nullptr) {}
};
Node* front;
Node* rear;
int size;
public:
Queue() : front(nullptr), rear(nullptr), size(0) {}
~Queue() {
while (front) {
Node* temp = front;
front = front->next;
delete temp;
}
}
void enqueue(T value) {
Node* newNode = new Node(value);
if (!rear) {
front = rear = newNode;
} else {
rear->next = newNode;
rear = newNode;
}
size++;
}
void dequeue() {
if (!front) return;
Node* temp = front;
front = front->next;
if (!front) {
rear = nullptr;
}
delete temp;
size--;
}
T getFront() {
return front->data;
}
bool empty() {
return front == nullptr;
}
};실전 예시
예시 1: LRU 캐시
LRU(Least Recently Used) 캐시가 요구하는 것은 “O(1)로 특정 키를 찾고, O(1)로 가장 최근 사용된 항목을 맨 앞으로 옮기고, O(1)로 가장 오래된 항목을 제거하는” 세 가지 연산이며, 이 셋을 모두 O(1)로 만족시키려면 단일 자료구조로는 부족합니다 — 이 구현이 unordered_map(O(1) 키 조회)과 이중 연결 리스트(O(1) 임의 위치 삽입/삭제)를 조합한 이유가 여기 있습니다. cache 맵은 키를 이중 연결 리스트의 노드 포인터로 직접 매핑해, “이 키가 리스트의 어디에 있는가”를 순회 없이 즉시 찾을 수 있게 하고, moveToFront(제거 후 맨 앞에 재삽입)는 포인터 몇 개만 바꾸는 O(1) 연산입니다. head와 tail을 실제 데이터가 없는 더미(sentinel) 노드로 둔 것도 중요한 설계입니다 — 이렇게 하면 “리스트가 비어 있는가”, “노드가 맨 앞/맨 뒤인가” 같은 경계 조건을 매번 특별히 검사할 필요 없이, addToFront/removeNode가 항상 “이전 노드와 다음 노드가 반드시 존재한다”는 가정 아래 동일한 코드로 동작할 수 있습니다.
class LRUCache {
private:
struct Node {
int key, value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map<int, Node*> cache;
Node* head;
Node* tail;
void addToFront(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
void removeNode(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToFront(Node* node) {
removeNode(node);
addToFront(node);
}
public:
LRUCache(int cap) : capacity(cap) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) == cache.end()) {
return -1;
}
Node* node = cache[key];
moveToFront(node);
return node->value;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node* node = cache[key];
node->value = value;
moveToFront(node);
} else {
if (cache.size() >= capacity) {
Node* lru = tail->prev;
removeNode(lru);
cache.erase(lru->key);
delete lru;
}
Node* newNode = new Node(key, value);
cache[key] = newNode;
addToFront(newNode);
}
}
~LRUCache() { // 남은 노드와 더미 노드까지 모두 해제
Node* curr = head;
while (curr) {
Node* next = curr->next;
delete curr;
curr = next;
}
}
};이 구현은 학습용으로 노드를 직접 관리하지만, 같은 구조를 std::list<std::pair<int,int>>와 std::unordered_map<int, std::list<...>::iterator>로 만들면 포인터 조작과 해제 코드를 전부 없앨 수 있습니다. list::splice로 노드를 맨 앞으로 옮기는 연산이 O(1)이고 반복자가 무효화되지 않기 때문입니다. 원래 코드에는 소멸자가 없어 캐시가 사라질 때 노드와 더미 노드가 모두 누수되었는데, 직접 구현할 때 이런 누락이 얼마나 쉽게 생기는지 보여 주는 예이기도 합니다.
예시 2: 그래프 (인접 리스트)
vector<vector<int>>로 그래프를 표현하는 “인접 리스트” 방식은, 각 정점 i에 대해 adj[i]가 그 정점과 연결된 이웃들만 저장하는 방식입니다 — 이는 V x V 크기의 2차원 배열 전체에서 연결 여부를 O(1)로 조회할 수 있는 “인접 행렬” 방식과 대비되며, 실제 그래프 대부분이 정점 수에 비해 간선 수가 훨씬 적은 희소(sparse) 그래프라는 점에서 메모리를 훨씬 절약합니다. BFS와 DFS는 똑같이 “모든 도달 가능한 정점을 방문한다”는 목표를 갖지만 그 순서와 구현 방식이 근본적으로 다릅니다 — BFS는 큐(선입선출)를 써서 가까운 정점부터 파도처럼 넓게 퍼져나가므로 “최단 경로”를 찾는 데 적합하고, DFS는 재귀(또는 스택)를 써서 한 방향으로 최대한 깊이 파고든 뒤 되돌아오므로 사이클 탐지나 위상 정렬 같은 문제에 자연스럽게 맞습니다. 두 알고리즘 모두 visited 배열로 이미 방문한 정점을 표시하는 것이 필수인데, 이 표시가 없으면 무방향 그래프에서 A→B→A처럼 왔다 갔다 하며 무한히 순회하는 문제가 생깁니다.
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 무방향 그래프
}
void BFS(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int curr = q.front();
q.pop();
cout << curr << " ";
for (int neighbor : adj[curr]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
cout << endl;
}
void DFS(int start) {
vector<bool> visited(V, false);
DFSHelper(start, visited);
cout << endl;
}
private:
void DFSHelper(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
DFSHelper(neighbor, visited);
}
}
}
};자주 발생하는 문제
문제 1: 메모리 누수
증상: 메모리 계속 증가
원인: 노드 삭제 안함
해결법: 소멸자에서 모든 노드 삭제
포인터 기반 자료구조(연결 리스트, BST, 큐)는 new로 만든 노드 하나하나를 프로그래머가 직접 추적해 delete해야 하며, 이는 std::vector나 std::unique_ptr가 자동으로 해 주는 일을 수동으로 재현하는 것입니다. 이 글의 모든 구현이 소멸자에서 반드시 모든 노드를 순회하며 해제하는 코드를 포함하는 것(연결 리스트의 while(head) 루프, BST의 destroyTree 후위 순회, 큐의 while(front) 루프)이 우연이 아니라, 자료구조 자체가 소유한 리소스를 그 자료구조의 수명이 끝나는 시점에 정확히 함께 해제해야 한다는 RAII 원칙을 각자의 구조에 맞게 구현한 것입니다 — 이 소멸자 로직을 빠뜨리면 자료구조가 소멸된 후에도 그 안의 노드들이 힙에 그대로 남아 프로그램이 실행되는 내내 메모리 사용량이 계속 증가합니다.
문제 1-2: 복사하면 이중 해제 (Rule of Three)
소멸자를 직접 만든 순간 반드시 함께 챙겨야 하는 것이 복사입니다. 위 LinkedList, BST, Queue, LRUCache는 모두 소멸자에서 노드를 해제하지만 복사 생성자와 복사 대입 연산자는 정의하지 않았습니다. 그러면 컴파일러가 만든 기본 복사가 포인터 값만 복사하므로, LinkedList<int> b = a; 뒤에 두 객체가 같은 노드들을 가리키고, 둘이 소멸될 때 같은 노드를 두 번 delete합니다. glibc에서는 free(): double free detected in tcache 2 메시지와 함께 프로그램이 중단되고, 함수에 자료구조를 값으로 넘기기만 해도 이 일이 생깁니다.
해결책은 둘 중 하나입니다. 복사가 필요 없다면 LinkedList(const LinkedList&) = delete;와 LinkedList& operator=(const LinkedList&) = delete;로 복사를 금지해 컴파일 에러로 막고, 필요하다면 노드를 하나씩 새로 만드는 깊은 복사를 구현합니다(C++11 이후라면 이동 생성자·이동 대입까지 다섯 가지를 함께 설계하는 Rule of Five). 가장 간단한 방법은 노드를 std::unique_ptr<Node>로 들고 있는 것인데, 그러면 복사가 자동으로 금지되고 소멸도 자동으로 처리됩니다. 다만 이 경우에도 긴 연결 리스트는 unique_ptr의 연쇄 소멸이 재귀처럼 동작해 스택이 넘칠 수 있으므로, 소멸자에서 반복문으로 하나씩 끊어 주는 처리가 여전히 필요합니다.
문제 2: 댕글링 포인터
증상: 크래시
원인: 삭제된 노드 접근
해결법: 삭제 후 포인터를 nullptr로 설정
delete는 그 포인터가 가리키던 메모리를 해제할 뿐, 포인터 변수 자체의 값을 바꿔주지 않습니다 — 그래서 delete temp 이후에도 temp는 여전히 그 (이제는 무효한) 주소를 담고 있고, 이를 다시 역참조하면 이미 해제된 메모리에 접근하는 use-after-free가 됩니다. 앞서 큐의 dequeue에서 다룬 것처럼, 한 포인터를 삭제한 뒤 다른 곳(rear)에서 여전히 그 주소를 참조하고 있다면 그 참조도 함께 정리해 주어야 하며, 이런 “삭제된 노드를 가리키는 두 번째 포인터”가 코드 전체에 흩어져 있을수록 추적하기 어려운 크래시의 원인이 됩니다. 삭제 직후 포인터를 nullptr로 설정해 두면, 설령 그 포인터를 실수로 다시 역참조하더라도 (조용한 메모리 손상 대신) 즉각적이고 진단하기 쉬운 널 포인터 크래시로 바뀐다는 것도 실무적인 이점입니다.
문제 3: 무한 루프
증상: 프로그램이 멈춤
원인: 순환 참조 또는 잘못된 포인터 연결
해결법: 디버거로 포인터 체크
이 문제는 흔히 두 가지 형태로 나타납니다 — 하나는 연결 리스트나 큐를 조작하는 코드가 실수로 next 포인터를 자기 자신이나 이전 노드로 되돌려 연결해, 순회 루프가 리스트의 끝(nullptr)에 결코 도달하지 못하고 같은 노드들을 계속 맴도는 경우입니다. 다른 하나는 앞서 그래프 절에서 다룬 것처럼 visited 배열 없이 BFS/DFS를 구현해, 무방향 그래프의 양방향 간선을 왔다 갔다 하며 영원히 종료하지 않는 경우입니다. 두 경우 모두 증상(프로그램 멈춤)은 같지만 원인은 다르므로, 디버거로 무한 루프에 걸린 지점을 멈추고 포인터 값들(next가 예상과 다른 노드를 가리키는가)이나 순회 상태(visited 배열이 실제로 갱신되고 있는가)를 직접 확인하는 것이 가장 확실한 진단 방법입니다.
FAQ
Q1: 직접 만든 연결 리스트를 함수에 넘겼더니 “double free detected”로 죽습니다.
A: 값으로 넘기면서 기본 복사 생성자가 포인터만 복사했기 때문입니다. 함수가 끝나며 복사본의 소멸자가 노드를 해제하고, 원본의 소멸자가 같은 노드를 다시 해제합니다. const LinkedList&로 넘기거나, 복사 생성자·대입 연산자를 = delete하거나 깊은 복사로 구현하세요.
Q2: 정렬된 데이터를 BST에 넣었더니 소멸자에서 크래시가 납니다.
A: 트리가 한쪽으로만 뻗어 높이가 n이 되고, 재귀 소멸자가 n단계 깊이로 호출되면서 스택이 넘친 것입니다. 반복문으로 해제하거나 균형 트리를 사용하세요.
Q3: 개방 주소법 해시 테이블에서 삭제 후 다른 키를 못 찾습니다.
A: 삭제한 칸을 빈 칸으로 되돌려 탐사가 거기서 멈췄기 때문입니다. 삭제된 칸은 묘비(tombstone)로 표시해 탐색은 계속 지나가게 해야 합니다.
Q4: 실무에서 직접 구현하나요?
A: 대부분 STL을 사용합니다. 직접 구현하는 경우는 할당기를 통제해야 하는 임베디드·게임 환경, 침투형(intrusive) 리스트처럼 표준 컨테이너로 표현하기 어려운 구조, 특정 워크로드에 맞춘 해시 맵 정도입니다.