ProjekinAja. Software Engineering Stage 1 · Foundations Lesson 1.7
● Stage 1 · Lesson 1.7

The Data Structures You'll Actually Reach For

Arrays, hashmaps, trees, queues, and sets as cost profiles, not implementations — choosing the structure is choosing the access pattern.

⏱ ~18 min read 🧠 Mental model ⚡ TraceLab debt

🎯 By the end you'll understand

Why picking a data structure is the same decision as picking a cost profile for your operations. The five structures you'll reach for in 95% of real work — array, hashmap, tree, queue, set — mapped by what each operation costs. Why TraceLab v0's find_run is a structural debt waiting to explode. And why a database index is just one of these structures wearing a costume — a preview that will pay off in Stage 3.

KEY INSIGHTThe wrong structure is invisible at demo scale

You don't choose a data structure because of how it's implemented. You choose it because of what it costs to find things, add things, and remove things — under the access pattern your program actually has.

TraceLab v0's find_run works fine with ten logged runs. It reads every line in the CSV to search for a name match. That's a list scan: O(n) per lookup. Log ten thousand runs and each search is 1,000× more expensive than your first demo. The structure didn't change. The scale did. The cost was always there — it was just invisible.

🔑 Hold onto this

Every data structure is a set of promises about cost. An array promises O(1) random access and O(n) scans. A hashmap promises O(1) lookups by key. A balanced tree promises O(log n) for everything, including sorted order. When you pick a structure, you are committing to its cost profile for the lifetime of that code. Pick the wrong one and you will not notice until production — because demo scale is always the wrong benchmark. The fix is to reason about access patterns first, then choose a structure whose cost profile matches.

CORE CONCEPTCost profiles: the four operations that matter

Every data structure you'll reach for can be evaluated on four axes. These are the only four that matter in practice — everything else is a variant or combination:

1

Lookup — find by key or value

Can you retrieve a specific item without scanning everything else? An array can't — it checks every element. A hashmap can — it hashes the key to a bucket in O(1). The question is: "given X, give me the thing associated with X." This is what find_run needs to do.

2

Insert — add a new element

Where does new data land? Arrays insert at the end in O(1) amortized, but inserting in the middle means shifting everything to the right — O(n). Linked structures insert anywhere cheaply but require O(n) to find the insertion point first. This is where appending to TraceLab's CSV is actually fine.

3

Range scan — find everything between A and B

Do you need "all runs with loss between 0.2 and 0.5"? A hashmap is useless for ranges — hashing destroys order. A sorted array can binary-search to the range boundary in O(log n) but inserting into a sorted array is O(n). A balanced BST does both in O(log n). This is why database indexes are almost always trees, not hashmaps.

4

Delete — remove a specific element

Deletion is often the most expensive operation for structures that otherwise look cheap. Arrays are O(n) unless you're popping the tail. Hashmaps are O(1). Trees are O(log n). Queues only allow deletion from one end — their whole identity is a constrained access order, which is what makes them useful.

Operation Array / list Hashmap / dict Balanced tree Queue / deque Lookup by key O(n) O(1) avg O(log n) not its job Insert (append) O(1) amort. O(1) avg O(log n) O(1) ends Range scan O(n) scan / O(log n) sorted O(n) — no order O(log n + k) not its job Delete by key O(n) O(1) avg O(log n) O(1) ends
Cost profiles at a glance. The cells marked O(n) are the expensive traps — fine at 100 rows, catastrophic at 100,000. k = number of results returned by a range scan.

That table is your decision tree. Before you write my_list = [], ask: what operations will I run most? If lookup by name dominates, that list is a slow hashmap. If you need sorted order and fast lookups, that's a tree. If you only ever push and pop from one end, that's a queue — and its constraint is its value, because a FIFO contract is something the rest of your code can depend on.

SEE ITStructure cost visualizer

Pick an operation stream — or use the TraceLab preset — and watch per-operation cost counters accumulate across all four structures side by side. The counters measure conceptual work units (comparisons, hash computations, pointer traversals), not wall-clock time, so the comparison is always deterministic. At the end, the winner banner shows which structure paid the least total cost for your access pattern.

⚙ Interactive · Structure cost visualizer

Fire an operation stream at four structures in parallel. Watch costs accumulate. The TraceLab preset reveals exactly where v0's lookup debt lives.

Array / list
lookup0
insert0
range0
delete0
total0
Hashmap / dict
lookup0
insert0
range0
delete0
total0
Balanced tree
lookup0
insert0
range0
delete0
total0
Queue / deque
lookup0
insert0
range0
delete0
total0

Select a preset and click "Fire operations" to animate the cost accumulation.

The TraceLab preset is the most important one to run at 10 K rows. Notice: the array's lookup counter climbs to n per search (every row checked), while the hashmap stays at 1. That factor of n is exactly what Lesson 1.6 called a "growing cost." At 1 M rows the hashmap is still 1 lookup per query; the array is doing a million. The structure you choose at demo scale with 100 rows is the structure that goes to production — and you won't re-examine it until it's on fire.

CORE CONCEPTThe big five: what each one actually is

Implementation trivia can be looked up. What you need to carry in your head is the access pattern each structure was built for — and the one thing it's bad at.

Array (Python: list)

A contiguous block of memory slots. The CPU can compute the address of element i in a single multiply-and-add — that's why random access is O(1). The downside is that "contiguous" constrains you: inserting in the middle shifts every subsequent element. Appending to the tail is amortized O(1) because Python pre-allocates spare capacity and doubles it when needed (a geometric growth strategy — see lesson 1.6's cost model). Arrays have better cache locality than any pointer-linked structure; a sequential scan of a Python list is fast not because the algorithm is clever but because the hardware prefetcher is.

💡 Python list vs array

A Python list is an array of pointers to heap objects — not a C-style contiguous array of values. A three-element list costs at least 56 + 8×3 = 80 bytes (header plus pointer slots), but CPython pre-allocates spare capacity, so sys.getsizeof([1, 2, 3]) returns ~88 bytes on modern CPython — the exact figure is version-dependent. NumPy's true value arrays are an order of magnitude more cache-friendly for numeric work. When you need compact numeric arrays in Python, that's numpy.ndarray or array.array.

Hashmap (Python: dict)

Hash the key to a slot index; store (key, value) there; resolve collisions (CPython uses open addressing). Lookup, insert, and delete are all O(1) average — this seems too good, and the catch is hiding in "average." Worst-case is O(n) when every key hashes to the same bucket, though a good hash function makes this astronomically unlikely for real data. The more important limitation is that a hashmap has no order. You cannot answer "give me everything between key A and key B" without scanning the entire table — hashing destroys the ordering information that would let you binary-search. CPython's dict preserves insertion order since 3.7, but that's incidental ordering from the implementation, not sorted order you can binary-search.

why_dict_wins.pyO(1) vs O(n)
# TraceLab v0 — the problem
def find_run(name):
    for line in open("runs.csv"):   # O(n) — full scan every time
        if name in line:
            return line.strip()

# Fixed — keep a dict in memory (or an index in a real DB)
runs = {}                              # load once at startup
with open("runs.csv") as f:
    for line in f:
        parts = line.strip().split(",")
        if parts:
            runs[parts[0]] = parts  # key = run name

def find_run_fast(name):
    return runs.get(name)             # O(1) — one hash computation

Balanced tree (Python: sortedcontainers.SortedList, database B-tree)

A tree that rebalances itself to keep height at O(log n). Every operation — lookup, insert, delete, finding the minimum — costs O(log n). For n = 1 million, that's about 20 comparisons. For n = 1 billion, it's 30. The constant factor is small because "20 comparisons" is a genuinely short path. The payoff over a hashmap comes when you need sorted order or range queries: "give me all runs with loss ≤ 0.3." A balanced tree can find the boundary in O(log n) and then walk the sorted order to collect results — O(log n + k) where k is the number of results. A hashmap on the same query would cost O(n), because it has no order to exploit.

Python's standard library doesn't ship a balanced BST (it omits a lot of advanced structures), but the sortedcontainers library is the well-regarded third-party option. In practice, you'll encounter balanced trees most frequently as B-trees inside databases — the structure behind every index you've ever created in SQL. More on this in the foreshadowing section.

Queue (Python: collections.deque)

A structure that constrains access: FIFO (first-in-first-out) queues only let you add to the tail and remove from the head; stacks (LIFO) only expose one end. This isn't a weakness — the constraint is the value. Code that pushes work items to a queue and pops them from the other end is expressing an ordering guarantee in the data structure itself. A deque implements a double-ended queue: O(1) push and pop on either side, O(n) random access (because it's a doubly-linked list of chunks, not a contiguous array). Use it wherever you need fast front/back access or explicit FIFO/LIFO ordering — task queues, BFS, sliding-window algorithms.

📖 Why not use a list as a queue?

You can — list.pop(0) removes the first element — but it's O(n) because every remaining element shifts left. With 100,000 items, that's 100,000 pointer moves per dequeue. collections.deque.popleft() is O(1) because a deque maintains a pointer to both ends. This is a concrete example of the structure choosing the access pattern: "use a list" sounds neutral, but it implicitly chose O(n) dequeue.

Set (Python: set)

A hashmap with no values — just keys. O(1) membership test, O(1) insert, O(1) delete. The one operation a set makes blazingly obvious and cheap is "is X in here?" Python's in operator on a list is O(n); on a set it is O(1). For deduplication, union, intersection, and difference operations, sets are the canonical tool. They come up constantly in data pipelines, feature engineering (which categories have I seen?), graph algorithms (visited nodes), and — crucially — anywhere you're checking membership in a large collection and wondering why it's slow.

set_vs_list_membership.pyO(1) vs O(n)
# n = 100,000 items
known = list(range(100_000))
known_set = set(range(100_000))

# "is 99,999 in known?"
99_999 in known      # O(n)   — scans ~100,000 elements
99_999 in known_set  # O(1)   — one hash + one equality check

# Real example: deduplicate run names
seen = set()
unique_runs = []
for name in all_run_names:
    if name not in seen:    # O(1) per check
        seen.add(name)
        unique_runs.append(name)

TRACELABDissecting v0's structural debt

TraceLab v0 has two structural problems, one more visible than the other. The debt table from Lesson 1.1 noted them as "to be repaid in Lessons 1.6–1.7." Let's do the accounting.

✗ find_run: list scan on a CSV file

The whole file is the "structure." Lookup is a linear scan. At 10 runs, this is fast enough to miss entirely. At 100,000 runs — a realistic number for a robot team running overnight rollouts — a single find_run call reads and parses 100,000 lines. If a dashboard queries 20 runs per page, that's 2 million line reads per page load. This is not hypothetical: production systems are routinely written this way, discovered months later when the data grows, and fixed in an emergency.

The right structure for "look up a run by name" is a hashmap keyed on run name. Load once at startup; query in O(1). But there is a second debt that only surfaces when you add queries like "show me all runs from today" or "find runs with reward > 10." A hashmap can't answer those cheaply — it has no order. That's when you need a balanced tree (or a real database with a B-tree index). The access pattern dictates the structure. TraceLab currently has neither.

Here is what a structurally-sound in-memory index for TraceLab looks like. This is not the full fix — the CSV-as-storage problem lives in Stage 3 — but it shows the pattern:

tracelab_index.pystructure upgrade
import csv
from collections import defaultdict

class RunIndex:
    """In-memory index over runs.csv. Paid for on first load; O(1) per lookup."""
    def __init__(self, path="runs.csv"):
        self._by_name = {}            # hashmap: name → row  (O(1) lookup)
        self._by_date = defaultdict(list)  # hashmap: date → [row, …] (O(1) lookup by date)
        with open(path, encoding="utf-8") as f:
            for row in csv.DictReader(f):
                self._by_name[row["name"]] = row
                self._by_date[row["date"]].append(row)

    def find(self, name):               # O(1)
        return self._by_name.get(name)

    def runs_on(self, date):            # O(1) + O(k) to return k rows
        return self._by_date.get(date, [])

# Range queries (e.g. loss < 0.4) still require a sorted structure or a scan.
# That's the job of an index in a real DB — Lesson 3.5 (databases) picks this up.

Notice that runs_on(date) is also O(1) now — we built a second hashmap keyed on date at load time. The loading cost (O(n) once) is paid once; every subsequent query is constant. This is the fundamental trade: upfront work to build an index, amortized over many queries. Every database index you've ever created makes exactly this trade.

IN PRACTICEDatabase indexes are just these structures in costume

When you write CREATE INDEX idx_loss ON runs(loss) in SQL, you are not doing something exotic. You are telling the database to maintain a B-tree — a generalized balanced tree optimized for disk block access — keyed on the loss column. Every time you add or update a row, the database updates the B-tree. Every range query like WHERE loss < 0.4 uses that tree to find the boundary in O(log n) and walks the sorted leaves to collect results, instead of scanning every row.

B-tree root splits key space loss < 0.3 loss ≥ 0.3 0.12, 0.18 → row ptrs 0.21, 0.28 → row ptrs 0.31, 0.37 → row ptrs 0.41, 0.49 → row ptrs 0.55, 0.62 → row ptrs 0.71, 0.89 → row ptrs
A B-tree index on loss. A range query "WHERE loss < 0.4" walks down from the root in O(log n) and then follows the leaf chain left-to-right, collecting row pointers. No full-table scan needed. The dashed lines connect sorted leaf nodes — the database walks them for range results. This is the exact data structure from the balanced-tree row above, wearing a database costume.

The other common database index structure is a hash index — a hashmap over a column, for pure equality queries like WHERE name = 'exp042'. Fastest possible lookup, useless for ranges. PostgreSQL supports both; MySQL's InnoDB defaults to B-tree for everything. When you read "add an index on this column," the cost model you're implicitly applying is the one from this lesson. Lesson 3.5 (databases) will make this explicit with real SQL EXPLAIN output — but you've already absorbed the structural reason.

🔑 The unifying pattern

Every data structure you reach for in application code has a database cousin. Arrays → sequential scans. Hashmaps → hash indexes. Balanced trees → B-tree indexes. The academic teaching and the production reality are the same structure. Understanding one gives you the other for free.

WEAKNESSWhere structural choices bite

✗ "It works in testing" — the demo-scale trap

The single most common structural mistake is validating with 50 rows and deploying to 500,000. An O(n) scan on 50 rows takes microseconds and never shows up in any profiler. The same code on 500,000 rows takes seconds per query and takes down the service at lunch. The structure was always wrong; the scale just made it visible. The correct habit: think about the access pattern before you write the data structure, not after. Ask "what does lookup, insert, and range-query cost here, at 100× my current dataset?"

✗ Reaching for a hashmap when you need order

Hashmaps look like they solve everything because O(1) lookup sounds unbeatable. But the moment someone asks "show me the top-10 runs by reward" or "all runs between these two dates," a hashmap requires a full O(n) pass to reconstruct the order that a sorted structure would have given for free. The pattern that bites: a system designed around dict-lookups that then needs reporting queries — and the author adds an O(n) sort every time instead of asking whether the right structure was chosen upfront.

✗ Using list as a queue

queue = []; queue.append(item); item = queue.pop(0) — this pattern appears in more production code than it should. pop(0) is O(n): it removes the first element and shifts every remaining pointer left. At 10 items this is invisible. At 10,000 items processed per second, it becomes the bottleneck. The fix is a one-word change: from collections import deque. This is precisely the kind of "wrong structure invisible at demo scale, fatal at production scale" scenario this lesson is about.

KEY INSIGHTHow this connects

  • Big-O as a Budget (1.6) — the cost notation you used to read this lesson's cost profiles; structure choice is applied Big-O.
  • The Network from First Principles (1.8) — next lesson; the same "what is actually happening at each layer" discipline applied to bytes on a wire.
  • Database indexes (Stage 3, Lesson 3.5) — the B-tree and hash index you met above, shown in real SQL with EXPLAIN plans and index design decisions. This lesson is your conceptual prerequisite.

The theme of this lesson is that structures are not implementation details — they are policy decisions that commit your code to a cost profile for its entire lifetime. Every time you declare a variable, you are implicitly choosing a structure. The engineers who debug the slowest systems are usually the ones who never made that choice explicitly.

GLOSSARYKey terms introduced

Access pattern
The mix of operations (lookup, insert, range scan, delete) that a piece of code actually performs on a data structure — the primary input to a structure-choice decision.
Cost profile
The set of Big-O bounds for each operation a data structure supports: what it costs to insert, look up by key, range-scan, and delete. Choosing a structure is choosing its cost profile.
Hashmap (dict)
A key-value store that hashes keys to bucket positions, giving O(1) average lookup, insert, and delete. No ordering — cannot binary-search for range queries.
Balanced tree (BST)
A tree that self-balances to maintain O(log n) height. Supports lookup, insert, delete, and range scans all in O(log n). The structure behind database B-tree indexes.
B-tree
A balanced tree generalized for disk-block access: nodes hold multiple keys, minimizing disk reads. The default index structure in most relational databases.
Deque
A double-ended queue supporting O(1) push and pop on both ends; implemented as a linked list of chunks in Python's collections.deque. Use instead of list.pop(0).
Set
A hashmap with keys only — no values. O(1) membership test, insert, and delete. The canonical tool for deduplication and fast membership checking in Python.
Index (database)
A data structure (usually a B-tree or hash table) that the database maintains alongside a table to allow fast lookup by a column without scanning every row — the same trade-off as building an in-memory dict over a CSV.

ACTIVE RECALLCheck your understanding

Answer in your own words first, then reveal.

1TraceLab v0's find_run scans every line of the CSV. What structure would fix the lookup cost, and what does it cost that a CSV scan doesn't?›

A hashmap (Python dict) keyed on run name. It fixes lookup from O(n) to O(1). The cost it adds: you must load the entire CSV into memory once to build the index, and you must keep it updated as new rows are appended. At scale, this trade is almost always worth it — O(n) to build once, then O(1) per query, versus O(n) per query every time. The real fix at production scale is a proper database with a B-tree index, but the structural principle is identical.

2A colleague says "I use a dict for everything — it's O(1) lookup, why would I use anything else?" What would you tell them?›

Hashmaps are excellent for point lookups, but they destroy ordering. Any query that needs sorted output or range results — "all runs with loss < 0.4", "the 10 most recent runs", "runs between these dates" — costs O(n) on a hashmap because there is no order to exploit. For those access patterns, a balanced tree (or a sorted list with binary search) is O(log n + k). The right structure depends on the access pattern, not on which structure has the best-sounding lookup cost. Also: queues have a specific FIFO/LIFO semantic that a dict can't express cleanly — structure encodes access policy.

3Why is a database B-tree index just a "data structure in costume"? What does CREATE INDEX idx_loss ON runs(loss) actually tell the database to do?›

It tells the database to build and maintain a B-tree keyed on the loss column. The B-tree is a balanced tree variant optimized for disk reads — nodes hold many keys so each node read fetches a full disk block. Every time a row is inserted or updated, the database updates this tree. Queries like WHERE loss < 0.4 walk the tree in O(log n) to find the boundary, then follow sorted leaf pointers to collect results — exactly like an in-memory balanced BST, just spread across disk blocks. The costume is "database"; the structure underneath is the same one from this lesson.

4You have a list of 50,000 visited node IDs in a BFS algorithm and need to check membership before exploring each neighbor. What is the structural mistake and the fix?›

Using a list for the visited set. node_id in visited_list is O(n) — with 50,000 visited nodes it scans up to 50,000 entries per neighbor check. BFS on a graph with 100,000 nodes and average degree 10 would perform up to 5 billion comparisons. The fix: visited = set(). node_id in visited_set is O(1). This is the membership-checking use case that sets exist for — same underlying hash table as a dict, no values stored. One-word change, orders-of-magnitude speedup.

Next: the network from first principles — bytes on a wire, the TCP/IP stack, and why HTTP is just text →