Custom Data Structures — Implement From Scratch¶
“You do not really understand a data structure until you have written it, broken it, debugged it under a timer, and then thrown it away and written it again.”
This file gives you the eight data structures that study partners most commonly ask you to implement, not just use. Each entry: goal, minimal C++ template you can memorize, complexity table, when to reach for it, and one LeetCode problem where it is the key.
All code below compiles under -std=c++20 -Wall -Wextra. Type each one out by hand, at least once, then again from memory.
(a) Union-Find (Disjoint Set Union) — with path compression + union by rank¶
Goal. Maintain a partition of {0, 1, ..., n-1} under two operations: find(x) returns x’s group representative; unite(a, b) merges the groups containing a and b. Both operations run in effectively-constant amortized time (α(n), the inverse Ackermann function — ≤ 4 for any n you will meet).
class DSU {
std::vector<int> parent, rank_;
public:
explicit DSU(int n) : parent(n), rank_(n, 0) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path halving
x = parent[x];
}
return x;
}
bool unite(int a, int b) {
a = find(a); b = find(b);
if (a == b) return false;
if (rank_[a] < rank_[b]) std::swap(a, b);
parent[b] = a;
if (rank_[a] == rank_[b]) ++rank_[a];
return true;
}
};
Operation |
Complexity |
|---|---|
|
Amortized O(α(n)) ≈ O(1) |
Space |
O(n) |
When to use. Anything about connectivity where you incrementally merge groups: Kruskal’s MST, cycle detection in an undirected graph as edges arrive, “number of islands II” (dynamic addition), account merging, redundant connection.
study problem. <phone_number_or_numberic_id_or_random_id_12>. Redundant Connection — the DSU archetype.
Trap. Forgetting to compress in find still gives correctness but blows up to O(log n) per operation, occasionally O(n). Always compress.
(b) Trie — with insertion, lookup, prefix, and delete¶
Goal. Multi-way tree indexed by prefix. Every node has up to 26 (or 128, or 256) children plus an is_end flag. Insertion, lookup, prefix-search: all O(L) in the length of the key.
struct TrieNode {
std::array<TrieNode*, 26> child{};
bool is_end = false;
};
class Trie {
TrieNode* root = new TrieNode();
public:
void insert(const std::string& w) {
TrieNode* cur = root;
for (char c : w) {
int i = c - 'a';
if (!cur->child[i]) cur->child[i] = new TrieNode();
cur = cur->child[i];
}
cur->is_end = true;
}
bool search(const std::string& w) const {
const TrieNode* n = find_node(w);
return n && n->is_end;
}
bool startsWith(const std::string& p) const {
return find_node(p) != nullptr;
}
// Returns true if word was present and deleted.
bool erase(const std::string& w) {
return erase_helper(root, w, 0);
}
private:
const TrieNode* find_node(const std::string& s) const {
const TrieNode* cur = root;
for (char c : s) {
int i = c - 'a';
if (!cur->child[i]) return nullptr;
cur = cur->child[i];
}
return cur;
}
bool erase_helper(TrieNode* node, const std::string& w, size_t i) {
if (i == w.size()) {
if (!node->is_end) return false;
node->is_end = false;
return has_no_children(node);
}
int idx = w[i] - 'a';
TrieNode* nxt = node->child[idx];
if (!nxt) return false;
bool should_delete_child = erase_helper(nxt, w, i + 1);
if (should_delete_child) {
delete nxt;
node->child[idx] = nullptr;
return !node->is_end && has_no_children(node);
}
return false;
}
static bool has_no_children(const TrieNode* n) {
for (auto* c : n->child) if (c) return false;
return true;
}
};
Operation |
Complexity |
|---|---|
Insert / search / prefix / erase |
O(L) time, O(L·Σ) space per key worst-case |
When to use. Autocomplete, dictionary lookup, word-search on grids, longest-common-prefix, IP-routing (byte-trie).
study problem. 212. Word Search II — the classic “trie + backtracking on grid” problem.
Trap. new in insert without matching delete in the destructor is a leak. In study code you can usually skip the destructor, but write a ~Trie() for production; it is a common follow-up question.
(c) Segment Tree — with lazy propagation (range update, range query)¶
Goal. Support arbitrary range queries (sum, min, max, gcd, …) and range updates in O(log n) each on an array of size n.
class SegTreeLazy {
int n;
std::vector<long long> tree, lazy;
void push_down(int node, int l, int r) {
if (lazy[node] == 0) return;
int mid = (l + r) / 2;
int lc = 2*node, rc = 2*node+1;
tree[lc] += lazy[node] * (mid - l + 1);
tree[rc] += lazy[node] * (r - mid);
lazy[lc] += lazy[node];
lazy[rc] += lazy[node];
lazy[node] = 0;
}
void update(int node, int l, int r, int ql, int qr, long long v) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
tree[node] += v * (r - l + 1);
lazy[node] += v;
return;
}
push_down(node, l, r);
int mid = (l + r) / 2;
update(2*node, l, mid, ql, qr, v);
update(2*node+1, mid+1, r, ql, qr, v);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
push_down(node, l, r);
int mid = (l + r) / 2;
return query(2*node, l, mid, ql, qr)
+ query(2*node+1, mid+1, r, ql, qr);
}
public:
explicit SegTreeLazy(int size) : n(size), tree(4*size, 0), lazy(4*size, 0) {}
void update(int l, int r, long long v) { update(1, 0, n-1, l, r, v); }
long long query(int l, int r) { return query(1, 0, n-1, l, r); }
};
Operation |
Complexity |
|---|---|
Build / update / query |
O(log n) per op, O(n) build |
Space |
O(4n) |
When to use. Range aggregate queries that also mutate. If updates are only point updates, use Fenwick (simpler, smaller constant). If it is offline, sometimes Mo’s algorithm beats it.
study problem. 307. Range Sum Query — Mutable — no lazy needed; upgrade to lazy for range-update variants (LC 715, 218).
Trap. Off-by-one in the push_down interval arithmetic. Draw a picture with n=4 the first three times you write this.
(d) Fenwick Tree (Binary Indexed Tree)¶
Goal. Prefix sums with point updates, in O(log n). Smaller code, tighter constant than segment tree — use this when you only need point-update + prefix-query.
class Fenwick {
int n;
std::vector<long long> bit;
public:
explicit Fenwick(int size) : n(size), bit(size + 1, 0) {}
void update(int i, long long delta) { // 1-indexed
for (; i <= n; i += i & -i) bit[i] += delta;
}
long long query(int i) const { // prefix sum [1..i]
long long s = 0;
for (; i > 0; i -= i & -i) s += bit[i];
return s;
}
long long range(int l, int r) const { // sum [l..r]
return query(r) - query(l - 1);
}
};
Operation |
Complexity |
|---|---|
update / prefix |
O(log n) |
Space |
O(n) |
When to use. Point update, prefix / range sum. Also 2D variant for prefix sums on a grid. Also “count inversions in an array” (classical Fenwick application).
study problem. 315. Count Smaller Numbers After Self — coordinate-compress + Fenwick, or a merge-sort variant.
Trap. Fenwick is 1-indexed. Off-by-one on the boundary between 0-indexed input and 1-indexed tree is the #1 bug.
(e) LRU Cache — list + unordered_map¶
Goal. O(1) get and put, evicting the least-recently-used key on overflow. Also revisited as Project P1.1 in Phase 1.
class LRUCache {
int cap;
std::list<std::pair<int,int>> lst; // front = most recent
std::unordered_map<int, std::list<std::pair<int,int>>::iterator> mp;
public:
explicit LRUCache(int capacity) : cap(capacity) {}
int get(int key) {
auto it = mp.find(key);
if (it == mp.end()) return -1;
lst.splice(lst.begin(), lst, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = mp.find(key);
if (it != mp.end()) {
it->second->second = value;
lst.splice(lst.begin(), lst, it->second);
return;
}
if ((int)lst.size() == cap) {
mp.erase(lst.back().first);
lst.pop_back();
}
lst.emplace_front(key, value);
mp[key] = lst.begin();
}
};
Operation |
Complexity |
|---|---|
get / put |
O(1) average |
Space |
O(capacity) |
When to use. Any bounded cache eviction. Backing store for a memoization table with a size limit. study partner favorite because it tests: hash map + doubly-linked list + iterator invalidation.
study problem. 146. LRU Cache directly.
Trap. std::list::splice is the O(1) magic move. Do not use erase + push_front — that invalidates iterators. Splice preserves them.
(f) Skip List (brief — for cultural literacy)¶
Goal. A probabilistic balanced-BST replacement: nodes at level k are in a linked list, and each node with probability 1/2 also appears at level k+1. Expected O(log n) search, insert, delete.
You will almost certainly not implement one in an study. Redis’s zset uses it, LevelDB’s memtable uses it, and it comes up in system-design and internals questions. You should be able to describe the structure and its tradeoffs (simpler than red-black, no rebalance), even if you cannot type it from memory.
Reference. William Pugh’s 1990 paper, ~10 pages: https://<phone_number_or_numberic_id_or_random_id_15>.cs.umd.edu/~pugh/projects/skiplists/paper.pdf
(g) B-Tree Node (brief — for internals literacy)¶
Goal. Balanced m-way tree that keeps the tree shallow, minimizing disk reads. Every internal node has between m/2 and m children; leaves at the same depth. This is what MySQL InnoDB, PostgreSQL, and most on-disk key-value stores use for their primary index.
Again, you will not implement this from scratch in an study. You must be able to:
Explain why B-tree beats binary tree for on-disk data (cache-line and page-size fit).
Describe insertion + split, deletion + merge, in words.
Distinguish B-tree vs B+-tree (B+ stores data only in leaves; leaves form a linked list for range scans).
Reference chapter. CLRS ch. 18. Read once; do not re-read.
(h) Monotonic Stack & Deque¶
Goal. A stack (or deque) whose contents are kept sorted while inserting, so that at any moment the extremes are known in O(1). Solves the entire “next greater element” family and “sliding window maximum” in linear time.
Monotonic stack template (next greater to the right):
std::vector<int> nextGreater(const std::vector<int>& a) {
int n = a.size();
std::vector<int> ans(n, -1);
std::stack<int> st; // indices; values in the stack strictly decreasing
for (int i = 0; i < n; ++i) {
while (!st.empty() && a[st.top()] < a[i]) {
ans[st.top()] = a[i];
st.pop();
}
st.push(i);
}
return ans;
}
Monotonic deque template (sliding-window max):
std::vector<int> maxSlidingWindow(const std::vector<int>& a, int k) {
std::deque<int> dq; // indices; a[dq.front()] is max of current window
std::vector<int> out;
for (int i = 0; i < (int)a.size(); ++i) {
if (!dq.empty() && dq.front() == i - k) dq.pop_front();
while (!dq.empty() && a[dq.back()] < a[i]) dq.pop_back();
dq.push_back(i);
if (i >= k - 1) out.push_back(a[dq.front()]);
}
return out;
}
Operation |
Complexity |
|---|---|
Per-element amortized |
O(1) |
Whole scan |
O(n) |
When to use. Next-greater / next-smaller, largest rectangle in histogram, sliding-window extremum, stock-span, sum of subarray minimums.
study problem. 239. Sliding Window Maximum and 84. Largest Rectangle in Histogram.
What most people get wrong¶
They read the code for these structures and think “I get it,” then try to write it in an study and freeze. The gap between reading and typing-from-memory is enormous. For each of (a)-(d) and (e), (h), do this drill: implement it once with the file open, close the file, then implement it again from memory. If the second implementation fails to compile in one shot, do it a third time tomorrow.
Union-Find is the single highest-return item on this list. Nearly every graph problem past week 15 uses it. Get it into fingers first.