Implementing Data Structures in C++: Linked List, BST, and Hash Table, and the Bugs Each One Hides
Key takeaways
Writing a linked list, BST, or hash table yourself is the best way to understand the standard containers, and the textbook versions all share bugs worth learning from: they break when copied, recurse too deep on bad input, or cannot delete safely. This guide walks through each implementation and what it leaves out.
Implementing data structures yourself is worth doing even though you will almost always use std::list, std::map, and std::unordered_map in real code. Writing them forces you to deal with the questions the standard containers answer for you: who owns each node, what happens when the container is copied, what a worst-case input does to the complexity, and why an operation that is O(1) on paper can be slow in practice.
The three implementations below are deliberately close to the versions found in textbooks and interview prep material. That makes them readable, but each one has at least one real bug or gap, and the sections after the code are about those gaps. Recognizing them is more useful than memorizing the code. The examples assume #include <iostream>, <vector>, <functional> and using namespace std;.
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;
}
};The bug: copying the list
This class has a destructor that deletes nodes, but no copy constructor or copy assignment operator. The compiler generates both, and they copy the head pointer, not the nodes. So after LinkedList<int> b = a;, both lists point to the same nodes. When b goes out of scope, its destructor deletes them, and when a is destroyed later, it deletes them again: a double delete, which is undefined behavior and often corrupts the heap (see C++ heap corruption). Passing the list by value to a function triggers the same bug, which is why it tends to appear far from the class definition.
This is the Rule of Three (Rule of Five with move operations): if a class needs a user-written destructor, it almost certainly needs user-written copy operations too, or needs them deleted. The minimal safe fix is LinkedList(const LinkedList&) = delete; and LinkedList& operator=(const LinkedList&) = delete;, which turns every accidental copy into a compile error. A complete version implements a deep copy and move operations. A different approach avoids the problem entirely: make next a std::unique_ptr<Node>, and the compiler refuses to generate copies on its own. Be aware that a long chain of unique_ptr is destroyed recursively, which can overflow the stack for lists with hundreds of thousands of nodes, so such a list still needs an iterative destructor.
In my experience, this is the most common bug in hand-written containers, in interview answers and production code alike. The class works in every test that only builds and prints one list, and the crash appears the first time someone stores the list in a std::vector (which copies or moves its elements when it grows) or returns it from a function in a way that makes a copy.
Smaller issues
push_back walks the whole list to find the end, which makes it O(n), and building a list of n elements with push_back costs O(n²). Keeping a tail pointer makes it O(1), at the cost of one more pointer to keep correct in remove (removing the last node must update tail). The functions also take T value by value, which copies the element once on the way in and again into the node. For a std::string that is an extra allocation per insert. Taking const T& (or T&& plus std::move) avoids it, and size should be std::size_t rather than int.
Finally, the FAQ answer above is worth taking literally: a linked list is rarely faster than a std::vector, even for insertions in the middle. Each node is a separate heap allocation, and walking the list follows pointers to unpredictable addresses, so almost every step is a cache miss. A vector moves elements with a fast memory copy over contiguous memory. For lists that fit in cache, finding the insertion point dominates, and the vector usually wins until the elements become large or expensive to move.
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
}The tree has the same copy problem as the list (a user-written destructor with compiler-generated copies), and the same fixes apply.
Worst case: sorted input
A BST is only O(log n) if it stays roughly balanced, and this one does nothing to stay balanced. Insert 1, 2, 3, …, n in order, and every node becomes the right child of the previous one. The tree is now a linked list with extra pointers: search is O(n), and building it is O(n²). Sorted or nearly sorted input is not an unusual edge case. It is what you get from IDs, timestamps, and data loaded from a sorted file.
The recursive helpers make it worse. Recursion depth equals tree height, so on a degenerate tree of 100,000 sorted keys, insertHelper, searchHelper, inorderHelper, and destroyTree each recurse 100,000 levels deep and can overflow the default stack (often 1 MB on Windows, 8 MB on Linux). Search and insert are easy to write iteratively with a loop that walks down the tree. destroyTree and in-order traversal need an explicit stack.
This is why production ordered containers are self-balancing. std::map and std::set are almost always implemented as red-black trees, which rebalance with rotations on insert and delete and guarantee O(log n) height. Writing a red-black tree is a good exercise, but it is long and easy to get wrong. If you need an ordered structure in real code, use std::map, or a sorted std::vector with std::lower_bound when the data is built once and then only searched, which is also far more cache-friendly.
What is missing: deletion
This BST has no remove, and deletion is the hard part. Removing a node with two children requires replacing it with its in-order successor (the smallest node in its right subtree) and then removing that successor from its old position. Forgetting to reconnect the successor’s right child is the classic bug mentioned in the FAQ, and it silently drops a whole subtree from the tree. Test deletion with a randomized comparison against std::set: insert and remove random keys in both, and compare the in-order output after each step.
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);
}
}
}
};This is an open addressing table with linear probing: all entries live directly in one array, and a collision moves the new entry to the next free slot. The alternative, separate chaining, keeps a small list of entries per bucket. That is what std::unordered_map uses, because the standard requires that references to elements stay valid when the table grows, which rules out moving entries around in a flat array. Open addressing is often faster, because a probe sequence reads neighboring slots in the same cache lines instead of following list pointers. That is why many high-performance hash maps (Abseil’s flat_hash_map, for example) use it and give up the reference stability guarantee.
Why the load factor limit matters
The 0.7 check is not arbitrary. With linear probing, occupied slots form contiguous runs (“primary clustering”), and a key that hashes anywhere into a run must walk to its end. As the table fills, runs merge and grow, and the expected probe length rises steeply: at 50% load a failed lookup inspects about 2.5 slots on average, at 90% it is about 50. Keeping the load factor below about 0.7 keeps probes short. It also guarantees that the while (table[...].occupied) loops terminate: in a completely full table, a lookup for a missing key would loop forever.
The missing operation: deletion
The table has no remove, and the obvious implementation is wrong. If you delete an entry by setting occupied = false, you break the probe chain for every key stored after it. Suppose A and B both hash to slot 3. A is in slot 3 and B was pushed to slot 4. Delete A by marking slot 3 empty, and get(B) starts at slot 3, sees an empty slot, and returns “not found”, even though B is sitting in slot 4. The standard fix is a tombstone: a third state, “deleted”, which lookups skip over but inserts may reuse. Tombstones accumulate and lengthen probes, so they must be counted toward the load factor and cleared during rehash.
This bug is my favorite example of why hash table code needs randomized testing. A test that inserts a few keys and removes one almost never triggers it, because it only appears when a colliding key sits after the removed one. A loop that performs thousands of random inserts, removes, and lookups against a std::unordered_map finds it within seconds.
Smaller issues
size >= capacity * 0.7 is checked even when the key already exists, so updating a value can trigger an unnecessary rehash. The entry type requires K and V to be default constructible, since table.resize builds empty entries, which rules out many key types. Capacity starts at 10 and doubles, and std::hash<int> is the identity function in the major standard libraries, so keys that are multiples of 10 (or other patterns that share a factor with the capacity) all land in the same few slots. Prime capacities, or a mixing step applied to the hash before the modulo, spread such keys more evenly. And the rehash function copies oldTable instead of moving it: vector<Entry> oldTable = std::move(table); avoids copying every key and value once more.
Testing hand-written containers
The bugs above share one property: none of them show up in a short example that builds a container, inserts a few values, and prints them. They need copies, large or sorted inputs, or specific sequences of removals. The most effective test for any container implementation is a differential test: run long random sequences of operations on your container and on the standard equivalent (std::list, std::set, std::unordered_map), and compare the results after every step. Build the test with AddressSanitizer enabled (C++ sanitizers), and it also catches the double deletes and leaks.