C++ Data Structures — Complete Guide
이 글의 핵심
template <typename T> class BST { private: struct Node { T data; Node left; Node right; Node(T val) : data(val),…
1. Linked List
Here is detailed implementation code using C++. Define a class to encapsulate data and functionality, process data with loops, and perform branching with conditionals. Understand the role of each part while examining the code.
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 (BST)
Here is detailed implementation code using C++. Define a class to encapsulate data and functionality and perform branching with conditionals. Understand the role of each part while examining the code.
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
Here is detailed implementation code using C++. Define a class to encapsulate data and functionality, ensure stability through error handling, process data with loops, and perform branching with conditionals. Understand the role of each part while examining the code.
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; // Linear probing
}
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 pos = probe(index, i);
table[pos].key = key;
table[pos].value = value;
table[pos].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++;
}
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);
}
}
}
};Summary
Key Points
- Linked List: Dynamic size, O(1) insertion at front
- BST: O(log n) search/insert (balanced), O(n) worst case
- Hash Table: O(1) average, collision handling crucial
- Implementation: Understand memory management and edge cases
When to Use
✅ Use custom implementation when:
- Learning data structures
- Interview preparation
- Constrained environments (no STL)
- Need specific customization
❌ Use STL when:
- Production code
- Time-critical projects
- Need proven reliability
- Standard operations sufficient
Best Practices
- ✅ Handle memory properly (destructors)
- ✅ Check edge cases (empty, single element)
- ✅ Consider cache locality
- ❌ Don’t reinvent wheel in production
- ❌ Don’t forget memory leaks
Related Articles
Master data structure implementation for deeper understanding! 🚀
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. Development blog post organizing C++ data structures. template
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- C++ queue/stack | ‘자료구조’ 완벽 정리 [BFS/DFS 활용]
- C++ set/unordered_set | ‘중복 제거’ 완벽 가이드
- C++ Algorithm Heap | ‘힙 알고리즘’ 가이드
이 글에서 다루는 키워드 (관련 검색어)
C++, data-structure, algorithm, implementation 등으로 검색하시면 이 글이 도움이 됩니다.