Lesson 2: Data Structures by Access Pattern

Choosing by read pattern, not by habit

Most people reach for a list because a list is what they reached for last time. The better habit is to ask one question before choosing: what will I do with this collection most often?

Four built-in structures, and the access pattern each one is built for:

list. An ordered, changeable sequence. Use it when order matters and you will mostly iterate or index. The accepted documents from Lesson 1 are a list because you append to the end and later walk through them in order.

dict. A mapping from keys to values. Use it when you will look things up by name or identifier. Rejection counts are a dict because you will ask "how many were duplicates?" rather than walking through every rejection.

set. An unordered collection of unique items. Use it when the only question you ask is "is this in here?" or when you need to eliminate duplicates. The hash set is a set for exactly that reason.

tuple. An ordered sequence that cannot be changed after creation. Use it for a fixed group of values that belong together and will not be modified, such as a coordinate pair or a function returning two things at once. Because tuples are immutable, they can be used as dictionary keys, which lists cannot.

A useful test when you are unsure. Say out loud what you will ask this collection. "Give me the third one" means list. "Give me the one called X" means dict. "Is X in here?" means set. "Here are two values that travel together" means tuple.

The cost of membership testing, insertion, and ordering

Structures differ in how their cost grows as they get larger. The notation for this is big O, which describes the shape of that growth rather than any exact timing.

O(1) means constant, so the operation costs the same whether the collection holds ten items or ten million. O(n) means linear, so cost grows in proportion to size. Ten million items cost a million times more than ten.

The single row that matters most is the first. Membership testing is O(n) in a list and O(1) in a set, and this is the most common avoidable performance mistake in Python.

Here is the difference in practice.

# Slow: each check scans the whole list
seen: list[str] = []
for doc_hash in hashes:
    if doc_hash in seen:        # O(n), and n keeps growing
        continue
    seen.append(doc_hash)

# Fast: each check is constant time
seen: set[str] = set()
for doc_hash in hashes:
    if doc_hash in seen:        # O(1) regardless of size
        continue
    seen.add(doc_hash)

These look almost identical and behave identically on small inputs. On 100,000 documents, the first performs roughly five billion comparisons and the second performs 100,000 lookups. The list version can take minutes while the set version takes a fraction of a second.

Why sets are fast. A set stores items by computing a hash, meaning a number derived from the item's value, and using it to decide where the item lives in memory. Checking membership computes the hash and looks in one place, rather than comparing against every item. This is also why set members must be hashable, which means immutable. You can put a string or a tuple in a set. You cannot put a list or a dict in one, because a value that can change would break the arrangement.

[IMAGE PROMPT M2-2
Purpose: Show visually why membership testing in a list scales badly while a set does not.
Visual type: Side-by-side mechanism comparison with a growth indicator.
Prompt: A clean educational comparison diagram in two panels. The left panel is headed "list: is x in it?" and shows a horizontal row of eight boxes labelled with sample values, with a magnifying glass icon positioned at the first box and small arrows stepping across every box in turn to the last, annotated "checks each item in turn" and marked "O(n)". The right panel is headed "set: is x in it?" and shows the same eight values arranged in scattered slots inside a grid, with a single arrow going from an input value labelled "x" through a small box labelled "hash" directly to one specific slot, annotated "computes location, looks once" and marked "O(1)". Beneath both panels runs a shared two-line comparison: "10 items: both fast" and "100,000 items: list slow, set fast".
Required elements: Sequential stepping arrows across all boxes on the left, a single direct arrow through a hash box on the right, the O notation on each panel, the shared two-line scale comparison beneath.
Style: Clean educational illustration, professional, uncluttered, high contrast, flat vector, consistent box sizing.
Layout: Two equal panels side by side with a thin divider, shared comparison text centred beneath both.
Text labels: "list: is x in it?", "set: is x in it?", "checks each item in turn", "computes location, looks once", "O(n)", "O(1)", "hash", "x", "10 items: both fast", "100,000 items: list slow, set fast".
Aspect ratio: 16:9
Accessibility: Distinguish the two mechanisms using arrow count and explicit text annotation rather than colour alone.
Avoid: Real code screenshots, decorative elements, tiny text, logos, watermarks, clutter.
Alt text: Comparison showing that checking membership in a list steps through every item in sequence at O(n) cost, while a set computes a hash to look in a single location at O(1) cost.
END IMAGE PROMPT]

When a list is still right. Do not convert everything to a set by reflex. Sets lose order and lose duplicates, and both of those are sometimes the information you need. If you want to know how many times each hash appeared, a set has already thrown that away. Choose by the question you will ask.

Nested structures and the shape of AI payloads

Real data is rarely flat, and API responses are where most people meet deeply nested structures for the first time. A typical model response looks roughly like this:

response = {
    "id": "resp_01H8X",
    "model": "some-model-v2",
    "content": [
        {"type": "text", "text": "Here is the recipe you asked for."},
        {
            "type": "tool_use",
            "id": "tool_01",
            "name": "search_recipes",
            "input": {"query": "carbonara", "max_results": 5},
        },
    ],
    "usage": {"input_tokens": 412, "output_tokens": 88},
}

Read the shape before writing any access code. This is a dict, whose content key holds a list, whose items are dicts of differing shapes. A text block has a text key. A tool use block has name and input keys and no text key at all.

That last detail is the trap. Writing response["content"][0]["text"] works until the day the first block is a tool call, and then it raises KeyError. The index [0] is an assumption about ordering that nothing guarantees.

Access nested data by shape, not by position.

def extract_text(response: dict) -> str:
    """Join all text blocks, ignoring blocks of other types."""
    parts = [
        block["text"]
        for block in response.get("content", [])
        if block.get("type") == "text"
    ]
    return "".join(parts)

This filters by the type field rather than trusting position, uses .get() with a default so a missing content key yields an empty result rather than an exception, and handles zero, one, or many text blocks identically.

Safe extraction from deep nesting. When you need a value several levels down, chained .get() calls with defaults keep the failure contained:

input_tokens = response.get("usage", {}).get("input_tokens", 0)

Each .get() returns an empty dict rather than None when the key is missing, so the next call in the chain still works. This is a useful pattern, though it has a real weakness: if the response shape is wrong, you get a silent zero instead of an error. Lesson 5 covers the better answer, which is to validate the whole structure once at the boundary instead of defending at every access.

Comprehensions as transformation

A comprehension builds a new collection from an existing one in a single expression. You have already seen one above. The mental model is: take each item, optionally keep it, transform it, collect the results.

# List comprehension: [transform for item in source if condition]
titles = [doc.title for doc in documents if doc.status == "valid"]

# Set comprehension: dedupe while transforming
unique_domains = {urlparse(doc.url).netloc for doc in documents}

# Dict comprehension: build a lookup
by_id = {doc.id: doc for doc in documents}

That third example is worth pausing on, because building a lookup dictionary from a list is one of the highest-value transformations you will write. If you find yourself scanning a list to find an item by its identifier inside a loop, build a dict once instead. You have converted an O(n) search repeated many times into an O(1) lookup repeated many times.

When not to use a comprehension. They are for transformation, not for side effects and not for complex logic. If a comprehension contains a nested conditional expression and two loops, a plain for loop is clearer and there is no prize for compressing it. And a comprehension written purely for its side effect, such as calling a function and discarding the result, builds a list of None values for no reason. Write a loop.

# Hard to read
results = [transform(x) if check(x) else fallback(x) for y in groups for x in y if x]

# Clearer
results = []
for group in groups:
    for item in group:
        if not item:
            continue
        results.append(transform(item) if check(item) else fallback(item))

Generator expressions. Swapping the brackets for parentheses produces a generator, which yields items one at a time instead of building the whole collection in memory.

total_chars = sum(len(doc.content) for doc in documents)

Nothing is materialised here, which matters when the collection is large. This is the seed of an idea that a later module develops fully.

collections: defaultdict, Counter, deque

The collections module provides specialised structures that genuinely reduce code. Three are worth knowing now.

Counter counts occurrences.

from collections import Counter

rejections = Counter()
rejections["duplicate"] += 1        # no need to initialise the key

# Or count a whole iterable at once
reasons = ["duplicate", "too_short", "duplicate", "not_readable"]
counts = Counter(reasons)
# Counter({'duplicate': 2, 'too_short': 1, 'not_readable': 1})

counts.most_common(2)
# [('duplicate', 2), ('too_short', 1)]

A plain dict requires checking whether a key exists before incrementing it. Counter treats missing keys as zero, and most_common() handles the sorting you would otherwise write by hand.

defaultdict supplies a default value for missing keys, which is what you want when grouping.

from collections import defaultdict

by_domain: defaultdict[str, list[str]] = defaultdict(list)
for doc in documents:
    by_domain[doc.domain].append(doc.id)

Without defaultdict, every append needs a guard checking whether the key exists yet. Note that the argument is the callable list, not an instance [], because it is called to create a fresh empty list for each new key. Passing [] would share one list between all keys, which is the same class of bug as a mutable default argument.

One caution. Reading a missing key from a defaultdict creates it, so a typo silently adds an entry rather than raising KeyError. Use it for building, and convert to a plain dict with dict(by_domain) before passing it somewhere that only reads.

deque is a double-ended queue, efficient at both ends.

from collections import deque

recent = deque(maxlen=100)          # keeps only the last 100 items
recent.append(message)              # oldest falls off automatically

queue = deque()
queue.append(task)                  # add to the right
next_task = queue.popleft()         # remove from the left, O(1)

Removing from the front of a list is O(n), because every remaining item shifts down one position. A deque does it in constant time. The maxlen parameter also gives you a fixed-size rolling window for free, which is useful for keeping recent conversation history or the last N results.

Concept check. You are processing 50,000 documents and need to know, for each source domain, how many documents came from it and whether you have already seen a particular document identifier. Which structures do you reach for?

Answer

A Counter keyed by domain for the counts, since you are incrementing a count per named key and will probably want most_common() at the end.

A set for the seen identifiers, since the only question asked of it is membership, and at 50,000 items the difference between a set and a list is the difference between instant and slow.

A defaultdict(list) would be right instead of Counter only if you needed the actual document identifiers per domain rather than just the count. Choose by the question you will ask later.