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
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)
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; // 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! 🚀
Frequently Asked Questions (FAQ)
Q. When would I use this in practice?
A. Development blog post organizing C++ data structures. template
Q. What should I read before this?
A. Follow the previous article or related articles links at the bottom of each post to learn in sequence. See the C++ series index for the full picture.
Q. Where can I study this more deeply?
A. Check cppreference and the relevant library’s official documentation. The reference links at the end of the article are also worth using.
Related Articles (Internal Links)
Other articles related to this topic.
- C++ queue/stack | ‘자료구조’ 완벽 정리 [BFS/DFS 활용]
- C++ set/unordered_set | ‘중복 제거’ 완벽 가이드
- C++ Algorithm Heap | ‘힙 알고리즘’ 가이드
Keywords Covered in This Article (Related Search Terms)
This article covers C++, data-structure, algorithm, implementation.