What you'll learn
You've met every major data structure. The real skill is choosing — matching the structure to what your program does most. This capstone gives you a decision guide, the master complexity cheat sheet, and the patterns that turn all of this into problem-solving.
A decision guide
Start from what you need to do most often, then reach for the structure built for it:
If you need…
Fast access by index / position
If you need…
Fast insert & delete at the ends
If you need…
Fast key → value lookup, no order
If you need…
Sorted data, ranges, ordered iteration
If you need…
Always grab the min or max
If you need…
Prefix search / autocomplete
If you need…
Model relationships / networks
If you need…
Track connected groups / merging
The master cheat sheet
Typical (average-case) complexities for the operations each structure is used for:
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
Array / dynamic array | O(1) | O(n) | O(1)* end | O(n) | O(n) |
Linked list | O(n) | O(n) | O(1) end | O(1)* end | O(n) |
Stack / Queue | O(n) | O(n) | O(1) | O(1) | O(n) |
Hash table | — | O(1) | O(1) | O(1) | O(n) |
Balanced BST | — | O(log n) | O(log n) | O(log n) | O(n) |
Heap | O(1) peek | O(n) | O(log n) | O(log n) | O(n) |
Trie | — | O(L) | O(L) | O(L) | O(Σ·nodes) |
B-tree | — | O(log n) | O(log n) | O(log n) | O(n) |
Graph (adj list) | — | O(V+E) | O(1) edge | O(E) | O(V+E) |
Note
* amortized. "Search" on a hash table means by key; on a heap it's O(n) because a heap only orders parent-vs-child, not siblings. L = word length, Σ = alphabet size.Interview patterns
Most coding problems are a structure plus a well-known technique:
| Pattern | Reach for | Typical problem |
|---|---|---|
Fast lookups / dedup | Hash set / map | Two-sum, count distinct |
Top-K / streaming max | Heap | K largest, median of a stream |
Shortest path / levels | BFS (+ queue) | Maze, word ladder |
Explore / backtrack | DFS (+ stack/recursion) | Permutations, islands |
Ordered ranges | Balanced BST / sorting | Interval problems |
Prefixes | Trie | Autocomplete, word search |
Grouping / connectivity | Union-Find | Number of connected components |
Why it all matters
Everything comes back to growth. The right structure turns an O(n) or O(n²) program into O(log n) or O(1) — the difference between instant and unusable at scale. One last look at what that means as n grows:
| Complexity | Name | Operations at n = 8 |
|---|---|---|
| O(1) | Constant | 1 |
| O(log n) | Logarithmic | 3 |
| O(n) | Linear | 8 |
| O(n log n) | Linearithmic | 24 |
| O(n²) | Quadratic | 64 |
| O(2ⁿ) | Exponential | 256 |
| O(n!) | Factorial | 40,320 |
Where to go next
- Practice on real problems — implement each structure once from scratch, then solve with them.
- Advanced topics: string algorithms (KMP, suffix arrays), computational geometry, advanced graph algorithms (max-flow, SCCs), and persistent data structures.
- Systems: see these structures in the wild — B+ trees in databases, LSM-trees in key-value stores, tries in routers, heaps in schedulers.
Key idea
Recap & quick check
Key takeaways
- Pick a structure by what your program does most: index, search by key, keep order, get the min, match prefixes, model relationships.
- Hash tables give O(1) average lookup but no order; balanced trees give O(log n) with order.
- Heaps give instant min/max; tries give prefix search; union-find tracks connectivity.
- Most interview problems are a structure plus a pattern (hashing, BFS/DFS, heap, two pointers).
- The right choice can turn O(n²) into O(log n) — that's why data structures matter.
Quick check
1. You need O(1) average lookup by key, and order doesn't matter. Use:
2. You must repeatedly extract the smallest element. Use:
3. You need sorted order AND fast range queries. Use:
4. Which pattern fits 'find the shortest path in an unweighted maze'?
🎉 That's the whole course. You've mastered data structures and the algorithms that bring them to life — from your first array to self-balancing trees and graph algorithms. Go build something fast.