Choosing the Right Data Structure

The “right” data structure is not the prettiest or most sophisticated one — it is decided by what you do with it most often. And making that call — seeing what the real problem actually needs — stays a human job, not the AI’s.

Picture three storage drawers: a clear box (you see every item instantly, but reaching the middle means digging through everything), an indexed cabinet (find the labeled slot and you’re done instantly, but you have no idea what sits next to what), and a stack of trays (grabbing the top one is instant, but the bottom one means unstacking everything above it). No drawer is “best” — the right question is “which item do I reach for most often?” Data structures work exactly the same way. An array is the clear box, a hash table is the indexed cabinet, a stack is the pile of trays.

Core idea

The heart of choosing a data structure is one sentence: “optimize for the dominant operation.”

Every structure is good at some things and bad at others; none is fast at everything. So instead of asking “which structure is best,” ask “in my program, what do I do with this data most often?”

Pick the structure that makes your most frequent operation fast, and let the occasional operation be a little slower — that trade is almost always worth it.

Questions to answer first:

• Do I look up by key often? → Hash Table
• Do I need the data to stay sorted? → Binary Search Tree (BST)
• Do I need a fast membership test (“have I seen this before?”) often? → Hash Table (hash set)
• Do I access in FIFO (first-in-first-out) or LIFO (last-in-first-out) order? → Queue or Stack
• Do I need the minimum/maximum repeatedly, without caring about the rest of the order? → Heap
• Do I ask range queries, e.g. “everything between 10 and 50”? → an ordered structure like a BST
• Do I mostly access by numeric index? → Array

Why does the difference between O(1), O(log n), and O(n) matter so much? Because as n grows, the gap between these curves does not grow linearly — it widens into a difference of thousands of times over. Try adjusting the chart below:

A decision framework

Walk these questions in order and stop at the first one that matches your main task:

1. Need the fastest lookup/insert/delete by key, and order doesn’t matter? → Hash Table — O(1) average
2. Need data sorted at all times, or range / nearest-neighbor queries? → (balanced) BST — O(log n)
3. Access most-recent first (undo, back button, bracket matching)? → Stack — push/pop O(1)
4. First in gets served first (job queue, BFS, buffer)? → Queue — enqueue/dequeue O(1)
5. Need the min/max repeatedly, without sorting everything? → Heap — insert/extract O(log n)
6. Access by numeric index frequently, size fairly fixed? → Array — access O(1)
7. Insert/delete at the ends very often, but rarely index into the middle? → Linked List — insert/delete at an end O(1)

Summarized as a decision flowchart

Start: what's the operation I do "most often" in my program?
│
├─ Lookup/insert/delete by key, order doesn't matter ────► Hash Table   O(1) avg
├─ Must stay sorted / range queries ──────────────────────► BST (balanced)  O(log n)
├─ Heavy membership testing (is it in here?) ────────────► Hash Set     O(1) avg
├─ Access most-recent first (LIFO) ───────────────────────► Stack        O(1)
├─ First in, first served (FIFO) ─────────────────────────► Queue        O(1)
├─ Need the min/max repeatedly ───────────────────────────► Heap         O(log n)
├─ Numeric index access, fixed size ──────────────────────► Array        O(1)
└─ Frequent insert/delete at the ends, rarely the middle ─► Linked List  O(1) at an end

Tip: if more than one answer applies (say, you need both key lookup and sorted order), that usually means you need two structures together — e.g. a dict paired with a heap. Don’t be afraid to combine them.

A decision table keyed by access pattern

Another way to look at the same problem: start from the “access pattern” your code performs most often, then match it to the structure built for exactly that pattern.

Access pattern	Example question in the code	Best-fit structure	Cost
Random access by index	“What’s the value at index 5000?”	Array	O(1)
Ordered iteration	“Walk everything from smallest to largest”	Balanced BST / sorted array	O(n) for the full walk, O(log n) per insert
Membership test	“Have I seen this value before?”	Hash Set	O(1) average
FIFO (first-in-first-out)	“Whoever arrived first gets served first”	Queue / deque	O(1)
LIFO (last-in-first-out)	“Undo the most recent action”	Stack	O(1)
Repeated min/max	“Who’s the most important one right now?”	Heap (priority queue)	O(log n)
Prefix / range query	“Everything between 100 and 500”	Balanced BST (or a Trie for string prefixes)	O(log n + k)

Operation-cost cheat sheet

Structure	Access	Search	Insert	Delete	Ordered?	Typical use
Array	O(1)	O(n)	O(n)	O(n)	No (insertion order)	Index access, fixed-size data
Linked List	O(n)	O(n)	O(1)*	O(1)*	No	Frequent insert/delete at the ends
Stack	O(n)	O(n)	O(1)	O(1)	No (LIFO)	Undo, back button, bracket matching
Queue	O(n)	O(n)	O(1)	O(1)	No (FIFO)	Job queue, BFS, buffers
Hash Table	—	O(1) avg	O(1) avg	O(1) avg	No	Lookup by key, counting, caches, membership tests
BST (balanced)	O(log n)	O(log n)	O(log n)	O(log n)	Yes	Always-sorted data, range queries, min/max
Heap	O(n)**	O(n)	O(log n)	O(log n)***	No (only the root is guaranteed)	Repeated extract-max/min, priority queue

* Linked-list insert/delete is O(1) only if you already hold a pointer to that position. If you must walk to find it first, it becomes O(n).

** A heap gives you O(1) access to the root value only (the min or max). Reaching any other element requires an O(n) walk — a heap makes no promise about the order of the rest.

*** This refers to popping the root (heappop) only. Deleting an arbitrary element by value still requires finding it first, which is O(n).

“Ordered?” means whether the structure maintains a sorted order automatically — a hash table guarantees no order, a BST gives you sorted order for free, and a heap only guarantees that “the root is the extreme value,” not the whole pile.

Try the hash table widget below. Notice that once you put more items in than there are slots, you get a collision — which is exactly why real hash tables have to resize periodically:

And compare it with a linked list — notice how prepend (insert at the head) is instantly cheap, but append (insert at the tail) or reaching the middle means walking node by node:

Six scenarios

1. A leaderboard that must always show ranks from highest to lowest The dominant work is “get the maximum” and “keep things sorted” while scores keep changing → use an ordered structure like a balanced BST (or a heap if you only ever need the top). Inserting a new score and reading order is O(log n), whereas re-sorting a list every time is O(n log n) per round — too slow.

2. Undo history in a text editor Every undo wants the most recent action first — that is LIFO → use a Stack. Push each action, pop the top one on undo. Both are O(1).

3. Phone-book lookup by name The dominant work is “given a name → return a number” as fast as possible, and order doesn’t matter → use a Hash Table (dict). Lookup by key is O(1) on average, versus O(n) to scan a list person by person.

4. A “recently opened items” cache that keeps at most N entries The dominant work is “add a new item at one end and drop the oldest at the other” — in one end, out the other, i.e. FIFO → use a Queue, specifically a deque that adds/removes at both ends in O(1) (in Python, collections.deque(maxlen=N) drops the oldest automatically). See the FIFO behavior in this widget:

5. An e-commerce site that frequently asks “which products cost between 100 and 500?” The dominant work is a range query over numeric values → use a balanced BST (or a sorted array if the data barely changes). Find the lower and upper bound in O(log n), then collect the k items in between for another O(k) — O(log n + k) total. A hash table can’t do this at all because it has no order to walk.

6. A duplicate-registration detector fed millions of incoming user IDs The dominant work is a pure membership test: “have I seen this ID before?” — nothing about order, nothing about any other value → use a Hash Set (Python’s set()). Each check is O(1) average. With a list, in is O(n) per check — over a million records that instantly becomes O(n²).

Real-world problem

A priority print queue

Problem: an office printer keeps receiving jobs; each has a “priority.” High-priority jobs must always print first, regardless of when they arrived.

The structure that looks right (but is wrong): many people grab a list and call sort() every time a job arrives, so the most important job sits at the front. It works, but re-sorting on every arrival is O(n log n) per job. With thousands of jobs flowing in and out per minute, it stalls immediately.

The structure that’s right (but not obvious): there are only two things we do often — “add a job” and “pull out the most important one.” We never actually need everything fully sorted; we only need the single most important item → the answer is a heap (priority queue), which adds a job and extracts the top in O(log n) without sorting the whole pile.

import heapq

pq = []
heapq.heappush(pq, (1, "print receipt"))     # (priority, job) — O(log n)
heapq.heappush(pq, (5, "print urgent contract"))
heapq.heappush(pq, (3, "print report"))

# Pull the most important job (smaller = higher priority in a min-heap) — O(log n)
print(heapq.heappop(pq))   # (1, 'print receipt')

Lesson: when you “need the single extreme element (max/min) again and again,” don’t rush to sort the whole pile — a heap gives you exactly that, far more cheaply.

Caveat: a heap is a poor choice if you frequently need to “walk everything in order” (that’s a BST’s or sorted list’s job). A heap is only great at “the single extreme, again and again.”

Exercises

Answer which structure you’d use and why (reason from the most frequent operation).

1. A system to check whether brackets ()[]{} in code are correctly matched and balanced. Which structure?

Answer

Stack — on an opening bracket, push; on a closing bracket, pop the top and check it matches. We always care about the most recently opened one — LIFO behavior. push/pop are O(1).

2. Store students with IDs, and very often look up “who is this ID?” at random. Which structure?

Answer

Hash Table (dict) keyed by ID. Lookup by key is O(1) on average and order doesn’t matter. Scanning a list would be O(n) per lookup.

3. A restaurant waitlist where first-come is first-served. Which structure?

Answer

Queue — first-come-first-served is FIFO. Add customers at the tail and call them from the head; both are O(1) (use collections.deque).

4. Store hourly temperatures for a whole year, and you often ask “what’s the value at hour index 5000?” Which structure?

Answer

Array (list) — index access is O(1) and the data size is fairly fixed. No need for anything more complex.

5. Store product prices and frequently ask “which products cost between 100 and 500?” Which structure?

Answer

A balanced BST (or another ordered structure), because range queries are efficient on already-sorted data — O(log n + k) where k is the number of results. A hash table can’t do this because it keeps no order.

6. The following code checks whether a user ID is a duplicate in a stream of 1 million records:

seen = []

def is_duplicate(user_id):
    if user_id in seen:      # ?
        return True
    seen.append(user_id)
    return False

What’s the total complexity for processing the whole stream, and how would you fix it?

Answer

user_id in seen on a list is O(n) because it must scan item by item. Called n times against a list that keeps growing, the total work becomes O(n²) — with a million records, that’s brutally slow.

Fix it by changing seen from a list to a set (Hash Set):

seen = set()

def is_duplicate(user_id):
    if user_id in seen:      # O(1) average
        return True
    seen.add(user_id)        # O(1) average
    return False

The whole stream is now O(n) total, because the dominant operation is a membership test — exactly what a hash set is built for.

7. You need to build “back” and “forward” buttons like a browser’s, for a page-visit history. Which structure?

Answer

Two stacks — one holds the history you can go “back” through, the other holds the history you can go “forward” through. On back, pop from the first stack and push onto the second (and vice versa on forward). This is a two-directional LIFO pattern; every push/pop is O(1).

8. Predict the output of this code (without running it):

import heapq

pq = []
for value in [7, 2, 9, 1, 5]:
    heapq.heappush(pq, value)

result = []
while pq:
    result.append(heapq.heappop(pq))

print(result)

Answer

[1, 2, 5, 7, 9]

Python’s heapq is a min-heap by default — no matter the order you push in, heappop always pulls out the smallest remaining value, one at a time. So pushing everything then popping everything produces a sorted ascending list (though doing this just to “sort” a whole list isn’t worth it — if you only need sorting, use sorted(), which is also O(n log n) but far more direct. A heap’s real strength is when data keeps streaming in and you need “the smallest right now” interleaved with new insertions).

AI Code Critique

You ask an AI for a “vote counter” that must return the “choice with the most votes” at any time. The AI replies:

votes = []   # stored as a list of choice names

def add_vote(choice):
    votes.append(choice)

def winner():
    # recount on every query
    counts = {}
    for v in votes:               # O(n)
        counts[v] = counts.get(v, 0) + 1
    best = None
    for choice, c in counts.items():   # O(m)
        if best is None or c > counts[best]:
            best = choice
    return best

Judge it: the AI stores every raw vote in a list, then recounts everything on every winner query — with a million votes and frequent queries, that’s O(n) per query. The most frequent operations are “add a vote” and “ask the winner,” so we should keep the counts in a dict from the start, not the raw votes. Rewrite it so asking the winner is faster.

Answer

from collections import Counter

counts = Counter()    # choice -> vote count

def add_vote(choice):
    counts[choice] += 1        # O(1)

def winner():
    return counts.most_common(1)[0][0]   # return the top one

Use a Counter (which is a dict) to hold counts directly. Adding a vote is O(1), and we no longer store every raw vote.

If you must ask for the “winner” so often that even scanning for the max is expensive, pair a heap (priority queue) with the dict so extracting the top is O(log n) — this is the case where a plain list is wrong but a dict (and maybe a heap) is the right answer.

🎮 Game Dev: Choosing the Right Data Structure

A game engine asks this lesson’s core question dozens of times per frame: inventory, collision checks, turn order, cooldowns, and undo/rewind are all “which operation happens most often?” in disguise. Get the structure wrong and a game that runs fine with 10 entities grinds to a halt at 500 — not because the logic is wrong, but because the data layer was optimized for the wrong access pattern.

Worked example: turn order + entity lookup in a tactics game

A tactics game needs two things every round: “who acts next?” (by speed/initiative) and “give me the unit with this ID” (to apply damage, check status, etc.). Naively, both get bolted onto a single list:

import heapq


class Unit:
    def __init__(self, unit_id: str, name: str, speed: int) -> None:
        self.id: str = unit_id
        self.name: str = name
        self.speed: int = speed


units: dict[str, Unit] = {
    "u1": Unit("u1", "Knight", speed=8),
    "u2": Unit("u2", "Rogue", speed=14),
    "u3": Unit("u3", "Mage", speed=11),
}

# Naive: a plain list, re-sorted every round — O(n log n) per round
turn_list: list[Unit] = list(units.values())


def naive_next_turn() -> Unit:
    turn_list.sort(key=lambda u: -u.speed)   # re-sort the WHOLE list, every time
    return turn_list[0]


# Scaled fix: a heap keyed by speed — insert/extract O(log n), no full re-sort
turn_heap: list[tuple[int, str]] = []
for u in units.values():
    heapq.heappush(turn_heap, (-u.speed, u.id))


def next_turn() -> Unit:
    neg_speed, unit_id = heapq.heappop(turn_heap)
    acting: Unit = units[unit_id]                    # entity-by-id: dict lookup — O(1)
    heapq.heappush(turn_heap, (neg_speed, unit_id))   # re-queue for the following round
    return acting


print(next_turn().name)   # Rogue (speed 14 acts first)

The dict answers “give me unit u3” in O(1) — exactly the access pattern every other system (damage, animation, UI) needs. The heap answers “who’s fastest right now?” in O(log n) without ever sorting the full roster — the naive list version pays O(n log n) on every single round, which is fine for 4 units and ruinous for 40.

Try adding units with different speeds above — the queue reorders itself around the priority, exactly like the heap in the code.

Inventory (slot UI) List show 20 slots in order

Inventory (crafting check) Dict “do I have 3x Iron Ore?”

Spatial queries (collision) Grid / Quadtree “who’s near (x, y)?”

Turn order Heap “who acts next?”

Entity-by-id lookup Dict “give me entity #482”

Cooldowns Heap “what’s ready next?”

Undo / rewind Stack “undo the last move”

Figure: seven game systems, the structure each one earns, and the access pattern that made the call.

Four more systems, four more calls

Inventory — list vs. dict. A 20-slot equipment grid that renders slots in a fixed order wants a list (index i is slot i, O(1)). But “does the player have a Health Potion?” or “how many Iron Ore do I have?” wants a dict keyed by item id — O(1) lookup instead of scanning every slot. Most real inventories use both: a list[Optional[Item]] for the UI grid, and a dict[str, int] counting stackable resources.

Spatial queries — grid or quadtree. “Which enemies are within melee range of the player?” done naively is “check every pair,” O(n²) — fine for 10 entities, catastrophic for 500. A spatial hash grid buckets entities by (x // cell_size, y // cell_size), so a query only checks the handful of entities in nearby cells. A quadtree does the same for uneven density (crowded areas subdivide further).

Toggle between brute-force and grid mode above — same entities, same query, very different work per frame.

Cooldowns — heap, once you have enough abilities. With 3-4 player abilities, just store ability -> ready_at_time in a dict and check all of them each frame — O(1) per ability, trivial either way. But a game with dozens of simultaneous timers (status effects across 50 units, say) benefits from a heap keyed by ready_at_time: “what expires next?” is O(log n) instead of scanning every timer every frame.

The dict backing entity-by-id lookup and small cooldown tables — watch what happens as it fills past its slot count.

Undo — stack, same as any other undo. A puzzle game’s “rewind last move” is identical to the text-editor undo earlier in this lesson: push a move snapshot before applying it, pop and restore on rewind. LIFO, O(1), nothing game-specific about it at all — which is itself the lesson: the pattern transfers even when the domain changes.

Exercises

Given the game feature and its access pattern, choose the structure and justify it.

1. A roguelike must render items in a UI grid in pickup order, and instantly answer “do I have a key for this door?” Which structure(s)?

Answer

Use both together: a list for the UI grid, since it must keep slot order (O(1) index access), and a dict keyed by item type for “do I have one of these?” (O(1) instead of scanning every slot, which is O(n)). This is the “combine two structures” tip from the main lesson in action.

2. A bullet-hell shooter has 300 enemy projectiles and one player hitbox, checked every frame. The feature is “which projectiles overlap the player’s hitbox this frame?” Which structure, and why?

Answer

A spatial hash grid — bucket projectiles by cell, then query only the player’s cell and its neighbors, O(1) average per frame instead of scanning all 300 projectiles every frame (O(n), or O(n²) if projectiles must also check against each other).

3. A turn-based RPG has a “haste” spell that changes a unit’s speed mid-encounter, requiring that unit’s position in the turn queue to be re-prioritized immediately. If turn order is already backed by a heap, what’s the catch, and how do you work around it?

Answer

Standard heaps don’t efficiently support “decrease the priority of an item that’s already inside” (decrease-key) — finding that item first is O(n). The common fix is lazy deletion: push a brand-new entry with the updated priority directly (O(log n)), and keep each unit’s current speed in a separate dict. When an old, stale entry is popped and its speed doesn’t match the dict, silently discard it and pop again — instead of trying to patch the heap in place.

4. An RPG has up to 40 simultaneous status-effect timers (poison, burn, stun…) across the battlefield, and must know “which status expires next?” every frame without scanning all 40. Which structure?

Answer

A heap (priority queue) keyed by expiry time — insert is O(log n) and peeking/popping the soonest-to-expire entry is also O(log n), exactly like the priority print queue from the main lesson. The only difference is that “priority” here is a timestamp instead of an importance level.

Challenge problems

Problem 1: design the data layer for a small top-down survival game.

The game needs three systems at once: (a) a player inventory with many item types, stackable counts, and a 5-slot hotbar that must keep its order; (b) an enemy spawner that must find “all enemies within 200px of the player” every frame to wake up their AI (hundreds of enemies may exist); and (c) a debug feature that rewinds the last 10 seconds. Propose a structure for each subsystem and justify it from its access pattern.

Approach

• Hotbar (5 slots): a fixed-size list — order must be preserved and access is by index, O(1).
• Stackable item counts: a dict[str, int] keyed by item type — check/increment/decrement is O(1) and order doesn’t matter.
• Enemies within 200px: a spatial hash grid, cell size tuned near the activation radius, querying only the cells around the player. Checking hundreds of enemies every frame at O(n) starts to hurt as the count grows; the grid keeps each query down to a few dozen candidates.
• 10-second rewind: not an unbounded stack, but a length-capped deque (collections.deque(maxlen=600) at 60 FPS), storing one state snapshot per frame. Once full, the oldest snapshot is dropped automatically — a LIFO/FIFO hybrid with a hard memory ceiling.

Problem 2: is a spatial grid worth it for a fighting game?

A fighting game’s hitbox system must find every overlap between an attacker’s active hitboxes and a defender’s hurtboxes, for up to 8 characters on screen, each of which may have several hitboxes active during move frames. Should you build a spatial hash grid for this, or is brute force enough? Justify with the actual numbers.

Approach

With n ≤ 8 characters and roughly 3 hitboxes each, that’s about 24 boxes total — a brute-force all-pairs check is about 24²/2 ≈ 276 comparisons per frame, comfortably microseconds and nowhere near a bottleneck at 60 FPS. Building and maintaining a spatial grid adds bucket-management overhead that only pays for itself once n climbs into the hundreds.

Rule of thumb: reach for a grid once n is large enough that O(n²) actually shows up in a profiler. For a fighting game’s small, fixed-size roster, the plain O(n²) nested loop is the right, unglamorous answer — the same “don’t over-engineer” lesson this course keeps repeating.

Going deeper

• MIT 6.006 — Introduction to Algorithms, opening lecture “Algorithmic Thinking, Peak Finding” and the data-structures series (free on MIT OpenCourseWare)
• Stanford CS161 — Design and Analysis of Algorithms, on choosing data structures and complexity analysis
• Skiena — The Algorithm Design Manual (3rd ed.), Chapter 3 “Data Structures” — the book that frames “which technique when” better than any other, with a war-story catalog at the back that compares data structures by real-world use case. Directly relevant to this lesson.
• CLRS — Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein), Part III “Data Structures” — rigorous complexity proofs for each structure.
• Sedgewick & Wayne — Algorithms (4th ed.), Chapters 3–4 — Java implementations of every structure in this table, with empirical measurements against the theory.
• Big-O Cheat Sheet at bigocheatsheet.com — a side-by-side complexity table for every common data structure