Complexity tables teach you that hash maps have O(1) lookup — then real work arrives and you're still defaulting to lists for everything, because nobody taught the decision procedure. This guide is that procedure: identify which operation your code performs most, match it to the structure optimized for exactly that, done. Six questions cover nearly every real decision.
Question 1: "Do I need to find things by key?"#
Use a hash map / dictionary.
Lookup by identifier — user by ID, config by name, count by word — is the hash map job: O(1) average access where a list needs O(n) scanning. The single highest-value habit in everyday code: any time you write x in some_list inside a loop, you wanted a set instead (the O(n²)-in-disguise trap).
Reach deeper only when requirements grow: need key-ordered iteration or range queries → balanced tree (TreeMap/sorted structures); need insertion-order preservation → ordered dict / LinkedHashMap.
Question 2: "Do I need uniqueness or membership testing?"#
Use a set.
Deduplication, "have I seen this?", tracking visited nodes (every graph traversal), tag intersections — sets give O(1) membership with automatic uniqueness. The list version of any of these is accidentally quadratic. Bonus fluency: set algebra (intersection, union, difference) replaces whole nested-loop functions in one call.
Question 3: "Does order matter — and which order?"#
Three sub-cases:
- Order = insertion sequence → dynamic array / list. The honest default for most collections; append is amortized O(1), iteration cache-friendly.
- Frequent insertions/removals at both ends → deque (double-ended queue). Sliding windows (the pattern) live here; inserting at a plain array's front is O(n) every time.
- Only the extremes matter ("smallest first," "top K") → heap / priority queue. O(log n) push/pop of extremes beats re-sorting an array repeatedly.
Question 4: "First in, first out — or last in, first out?"#
Processing order is a data structure choice:
- LIFO (undo stacks, parsing, DFS) → stack: push/pop on top
- FIFO (task queues, BFS, buffering) → queue: enqueue back, dequeue front
Both are trivially arrays/deques underneath — the value is naming the discipline. Code reading queue.pop(0) on a Python list is silently O(n); say "BFS" out loud and the right container follows.
Question 5: "Nested/hierarchical relationships?"#
Trees for hierarchies, graphs for arbitrary connections.
File systems, org charts, DOM → trees (parent-child, one path between nodes). Social networks, dependency resolution, maps → general graphs (cycles allowed). The interview-flavored insight: grids are graphs too — each cell connected to neighbors — which unlocks BFS/DFS machinery for maze/route problems.
Question 6: "Range queries over changing data?"#
The advanced tier, worth recognizing on sight:
- Prefix sums: many queries of "sum of elements i..j" over mostly-static data → precompute once, answer each query O(1)
- Sorted containers / binary search: "closest value ≥ X" repeatedly → keep data sorted, search O(log n)
- Segment trees / BITs: ranges and frequent updates → O(log n) per operation
Rare in daily code, disproportionately common in interviews' harder slots.
The decision table#
| Your code says... | Reach for |
|---|---|
| "find by ID/name/key" | hash map |
| "already seen?" / unique items | set |
| "just collect things" | dynamic array |
| "add/remove at both ends" | deque |
| "always process the smallest/biggest" | heap |
| "process in arrival order" | queue |
| "backtrack / nest / undo" | stack |
| "hierarchy" | tree |
| "connections/network" | graph |
| "repeated range sums" | prefix sum |
Worked example: the refactor reflex#
# Before: O(n²) — 'in' scans the whole list each iteration
result = []
for item in items:
if item not in result:
result.append(item)
# After: O(n) — set tracks membership, list preserves order
seen, result = set(), []
for item in items:
if item not in seen:
seen.add(item)
result.append(item)
Same output, same readability, categorically different scaling. That transformation — spotting the operation (membership test), matching the structure (set), preserving the requirement (order via companion list) — is the entire skill this guide teaches. Interviews test it directly (complexity analysis); production rewards it constantly.
Related: Big-O from real code · DSA patterns · 12-week plan
