Data Structures You'll Reach For
You don't need to know every exotic data structure. You need fluency in the ones that come up over and over, and a working understanding of when each shines.
The essentials
Arrays & Strings
The foundation. Master in-place manipulation, two-pointer techniques, and prefix sums. Most "easy" problems live here, and they're often where candidates over-engineer.
Hash Maps & Sets
Your O(1) lookup tool. Use for deduplication, frequency counts, and lookups while iterating. If you find yourself writing nested loops, ask whether a hash map collapses one of them.
Linked Lists
Cleaner mental model than implementation in most languages. Know how to: traverse with one or two pointers, reverse iteratively and recursively, detect a cycle.
Stacks & Queues
Stacks for matching/parsing/backtracking; queues for BFS and producer-consumer. A monotonic stack is worth its own afternoon — it shows up in "next greater element" style problems.
Trees
- Binary trees — DFS (preorder/inorder/postorder) and BFS (level-order).
- Binary search trees — in-order traversal yields sorted output. Worth memorizing.
- Tries — prefix-based lookup. Comes up in autocomplete and word-search problems.
Heaps / Priority Queues
The right tool for "top k" and streaming problems. Know when min-heap vs max-heap is correct, and the trick of using two heaps for medians.
Graphs
Adjacency list is the default representation. Know:
- BFS (shortest path on unweighted graphs),
- DFS (cycle detection, connected components),
- Dijkstra (shortest path on weighted graphs),
- Topological sort (for DAGs).
Complexity cheat sheet
The numbers you should be able to state without thinking:
| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | Insert/delete O(1) at end |
| Hash Map | — | O(1)* | O(1)* | O(1)* | *Amortized, worst-case O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | Constant-time at known position |
| Stack / Queue | — | O(n) | O(1) | O(1) | Push/pop only |
| Binary Heap | — | — | O(log n) | O(log n) | Peek O(1) |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | Red-black, AVL |
| Trie | — | O(k) | O(k) | O(k) | k = key length |
| Hash Set | — | O(1)* | O(1)* | O(1)* | Same caveats as Hash Map |
If you can recite this from memory, you're already ahead of most candidates.
What you can usually skip
Unless the role specifically calls for it, you don't need to drill: red-black trees, B-trees, Fibonacci heaps, segment trees, or splay trees. They almost never appear in software engineering interviews outside of specialized teams.
How to remember the operations
Build a 1-page cheat sheet of operations and complexities for each structure. Re-derive it from memory once a week for 3 weeks. After that, it's permanent.