C++ 자료구조 | "직접 구현하기" 연결리스트/트리/해시테이블
이 글의 핵심
C++ 자료구조에 대해 정리한 개발 블로그 글입니다. template <typename T> class BST { private: struct Node { T data; Node left; Node right; Node(T val) : data(val),…
1. 연결 리스트 (Linked 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;
}
};2. 이진 탐색 트리 (Binary Search Tree)
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
}3. 해시 테이블 (Hash Table)
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;
}
}
}
};4. 스택 (Stack)
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();
}
bool empty() {
return data.empty();
}
int size() {
return data.size();
}
};5. 큐 (Queue)
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 캐시
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);
}
}
};예시 2: 그래프 (인접 리스트)
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: 메모리 누수
증상: 메모리 계속 증가
원인: 노드 삭제 안함
해결법: 소멸자에서 모든 노드 삭제
문제 2: 댕글링 포인터
증상: 크래시
원인: 삭제된 노드 접근
해결법: 삭제 후 포인터를 nullptr로 설정
문제 3: 무한 루프
증상: 프로그램이 멈춤
원인: 순환 참조 또는 잘못된 포인터 연결
해결법: 디버거로 포인터 체크
FAQ
Q1: STL을 써도 되는데 왜 직접 구현하나요?
A:
- 면접 준비
- 내부 동작 이해
- 특수한 요구사항
Q2: 어떤 자료구조를 먼저 배워야 하나요?
A: 배열 → 연결리스트 → 스택/큐 → 트리 → 그래프
Q3: 시간복잡도는?
A:
- 연결리스트: 삽입 O(1), 탐색 O(n)
- BST: 평균 O(log n), 최악 O(n)
- 해시테이블: 평균 O(1), 최악 O(n)
Q4: 실무에서 직접 구현하나요?
A: 대부분 STL을 사용하지만, 특수한 경우 직접 구현합니다.
Q5: 자료구조 학습 리소스는?
A:
- “Introduction to Algorithms” (CLRS)
- LeetCode, 백준 문제 풀이
- visualgo.net (시각화)
Q6: 포인터가 어려워요!
A: 그림을 그려가며 이해하세요. 디버거로 포인터 값을 확인하는 것도 도움이 됩니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ STL 알고리즘 | “자주 쓰는 함수” 20개 총정리
- C++ queue/stack | “자료구조” 완벽 정리 [BFS/DFS 활용]
- C++ 알고리즘 | “STL algorithm” 핵심 정리
실전 체크리스트
실무에서 이 개념을 적용할 때 확인해야 할 사항입니다.
코드 작성 전
- 이 기법이 현재 문제를 해결하는 최선의 방법인가?
- 팀원들이 이 코드를 이해하고 유지보수할 수 있는가?
- 성능 요구사항을 만족하는가?
코드 작성 중
- 컴파일러 경고를 모두 해결했는가?
- 엣지 케이스를 고려했는가?
- 에러 처리가 적절한가?
코드 리뷰 시
- 코드의 의도가 명확한가?
- 테스트 케이스가 충분한가?
- 문서화가 되어 있는가?
이 체크리스트를 활용하여 실수를 줄이고 코드 품질을 높이세요.
관련 글
- 배열과 리스트 | 코딩 테스트 필수 자료구조 완벽 정리