Data Structures — list, tuple, dict, set (when to use what)

Review boundary and corrected contracts

Dictionary insertion order is guaranteed in Python 3.7+. Named tuples are hashable only if their fields are hashable. Counter's binary subtraction omits nonpositive counts (subtract() can retain them); a full bounded deque discards from the opposite end on append, unlike a blocking work queue. The timing script is illustrative, not a universal speed ratio.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Compare built-in data structures for a read/write pattern and justify the choice using operation costs and semantics.

Why this session exists

Repeated list membership is a common avoidable cost: a scan is O(n), while set membership is expected O(1) under ordinary hashing assumptions. Building the set also costs time and memory, so choose it when repeated membership queries justify that work. This session develops that decision alongside order, mutability and key-value lookup, then uses six collections helpers in concrete examples.

You will be able to

• Choose between list, tuple, dict, set, and frozenset for a stated workload — with Big-O justification.

• Reach for the right collections helper: Counter for tallying, defaultdict for grouping, deque for FIFO/LIFO, namedtuple for tiny records.

• Diagnose the ‘quadratic list search’ perf bug on sight and know the one-line fix.

• Explain why dict is O(1) but sometimes isn't (hash collisions, custom __hash__).

• Reason about memory: a dict of 1M small items vs a list of 1M small items — order of magnitude estimate.

Prerequisites

• S005 — Python Variables & Types — mutability rules matter here.
• S006 — Control Flow — comprehensions all over.
• S007 — Functions — you'll pass structures around.

Pre-read · skim before the session (30 min total)

Further reading: Python Tutorial · Data Structures

Further reading: Time Complexity of Python Built-ins

Further reading: collections — Container datatypes

(a) Intuition · 5 min

Data structures are tools with different edges

Real: Every tradesperson has a hammer, a screwdriver, pliers, a wrench. A senior tradesperson picks the right one in 2 seconds. A junior tries to use a hammer on everything and blames the wall when it doesn't work. Python's built-in data structures are the same. Each is optimised for one job. Using a list as a set (‘I'll just check x in the\_list’) works — until the list has 100,000 items and an absent or late-hit lookup scans most or all of the sequence.

 
    Concretely: list is an ordered array. tuple is an immutable list. dict is a hash table (key → value). set is a hash table without values. Each supports fast operations in one dimension and slow operations in the other.
    Big-O tells you which. If your code hits an operation in a hot loop, and that operation is O(n) for your structure but O(1) for another — switch. The change is usually one line.
  

The five-item decision matrix

Match the shape of your data + query to a structure

• Ordered, mutable, index-access — LIST. Default when you need a resizeable sequence.

• Ordered, IMMUTABLE — TUPLE. Fixed records and function return groups; usable as a dict key only when every element is hashable.

• Key → value lookup — DICT. When you'll ask ‘what value is stored under this key?’ millions of times.

• Unique items, ‘is X in this collection?’ — SET. Membership tests, dedup, set algebra (union, intersect, diff).

• Immutable set (needs to be a dict key or set element) — FROZENSET. Rare but critical when it matters.

The single biggest perf mistake in beginner Python

ClassName: mt-2 rounded bg-black/80 p-2 text-xs text-emerald-300

# BAD — O(n) per membership check, O(n×m) overall valid_ids = [1, 2, ..., 100_000] # a list for incoming in requests: if incoming.id in valid_ids: # may scan the whole list process(incoming)

# FIX — O(1) per check, O(n+m) overall (n to build the set, m checks) valid_ids = {1, 2, ..., 100_000} # a set (or frozenset)

The example is schematic: ... stands for omitted IDs, not an executable range literal. Build set(valid_ids) once when the values are hashable and membership dominates; measure construction as well as lookup before deciding it pays off.

A quick history

Python 2.3 introduced the sets module; Python 2.4 added built-in set and frozenset, and introduced collections with deque—not all six helpers at once. Later additions expanded that toolkit. Python 3.7 made dictionary insertion order a language guarantee. That did not turn dict into a key-sorted map or eliminate OrderedDict's specialized reordering operations.

(b) Matching operations to Python containers · 15 min

The Big-O cheat sheet you'll refer to for years

Container choice is not just about which literal looks convenient. Pick an operation you will repeat—membership, indexed access, or removal from the front—and compare its cost across the structures below.

The contrast between list membership and hash lookup is the one to carry into the timing exercise: the same membership question can require a scan or an average constant-time lookup. These bounds assume bounded-cost hashing and equality and ordinary collision behavior. Union must account for both inputs and can return their combined size; it cannot generally cost only the smaller input's length. Keep the semantic requirements too—order, uniqueness, and mutability decide whether that faster structure is a suitable replacement. CPython's deque uses a non-circular doubly linked chain of fixed-length blocks, not one circular linked node per item; see the CPython 3.14.0 implementation.

The four built-ins side by side

Name: list

Tagline: Ordered, mutable, indexed

• [1,2,3]

• append/pop (end): O(1) amortised in CPython; an individual resize can cost O(n)

• in / insert middle: O(n)

• Use for: sequence of items, order matters

Name: tuple

Tagline: Ordered, IMMUTABLE, indexed

• (1,2,3)

• hashable (if elements are)

• Use for: fixed-length records, dict keys, function returns

• Slightly less memory than list

Name: dict

Tagline: key → value, hashed

• {'a':1,'b':2}

• get/set/in: O(1) avg

• Ordered by insertion (3.7+)

• Use for: lookup by name, tallies, indexes

Name: set

Tagline: Unique, unordered, hashed

• {1,2,3}

• add/in: O(1) avg

• No duplicates

• Use for: dedup, membership tests, set algebra

The six collections helpers you should reach for on reflex

Every Python dev's daily toolkit

Name: Counter

Desc: Tally occurrences of hashable items. Counter('abracadabra') → {a:5, b:2, r:2, c:1, d:1}. .most\_common(3) gives top-3.

Name: defaultdict

Desc: Dict whose missing-key d[k] lookup calls a factory and stores its result. defaultdict(list) creates a list for each new grouping key; .get(k) does not call the factory.

Name: deque

Desc: Double-ended queue with approximately O(1) append/pop at either end. A bounded deque provides a rolling-buffer interface: appending to a full deque discards from the opposite end; it is not a blocking queue or necessarily a circular implementation.

Name: namedtuple

Desc: Tuple with named fields. Point = namedtuple('Point', 'x y'). Fields cannot be rebound, but a field may refer to a mutable object. Hashable only when all fields are hashable; consider a dataclass for richer record behavior.

Name: OrderedDict

Desc: Was essential pre-3.7; now mostly redundant. Still useful for move\_to\_end() (LRU caches) and popitem(last=False) (FIFO).

Name: ChainMap

Desc: Layer multiple dicts as one view. ChainMap(cli\_args, env\_vars, defaults) — search order is left-to-right. Great for config precedence.

The decision tree

Do you need ORDER?

Desc: If yes → list, tuple, deque, or dict (dicts preserve insertion order since 3.7).

Do you need UNIQUENESS?

Desc: If yes → set or frozenset. If no → list or tuple.

Do you need KEY→VALUE?

Desc: If yes → dict. Consider defaultdict or Counter for common patterns.

Do you MUTATE it?

Desc: If the container must change → list/dict/set. For a fixed sequence or fixed set → tuple/frozenset. A tuple used as a key also requires hashable elements.

Do you push/pop at BOTH ends?

Desc: If yes → deque (approximately O(1) at either end). A list has no popleft method; its pop(0) is O(n).

The mental model to hold

One line: match query pattern to structure

List for order + index. Set for membership + uniqueness. Dict for key-value lookup. Tuple/frozenset when you need immutability. Deque for FIFO/LIFO. If your hot loop mismatches — swap. That's the whole game.

Myth: "A dict lookup is O(1), so dicts are always the fast choice. And x in my_list versus x in my_set — both are just membership tests, the difference can't matter much."

Truth: Hash lookup is expected O(1) with bounded-cost hashing/equality and ordinary collisions. List membership is O(n) in the worst case; it can stop early on a match. Repeating a length-n scan n times can make a loop O(n²), whereas building a set and probing it n times is expected O(n). Actual timings depend on the values, hit positions and interpreter.

Why: Because the syntax is identical. in works on both, returns a membership answer, and gives no hint that one may scan the container. Python deliberately hides the cost behind a uniform interface, which is excellent for readability and terrible for cost intuition. The trap is specifically the nested form: a loop over n records that does if record.id in known_ids against a length-n list can be quadratic, while small fixtures can hide the cost. It is an accidental-quadratic pattern worth checking in data code.

Test: Same code, one word changed:import timeit n = 100_000 lst = list(range(n)); st = set(lst)

# worst case: the item is absent, so list must scan all n print(timeit.timeit(lambda: (n+1) in lst, number=100)) print(timeit.timeit(lambda: (n+1) in st, number=100)) # the set version is not 'a bit' faster - it is a different complexity class

Question: Why does list.append count as O(1) when the underlying array must sometimes be reallocated and every element copied? A single append can genuinely cost O(n) — so where does the O(1) come from?

Premise: A Python list is a contiguous array of pointers, which is what makes lst[i] a single address computation.

Because: random access in constant time requires elements at predictable addresses

Premise: Contiguity means capacity is fixed at allocation. Growing past it may require allocating a new block and copying every existing pointer—an O(n) worst-case operation.

Because: an allocator may extend a block in place, but cannot guarantee adjacent free space; the worst case requires relocation

Premise: If the new block were only one slot bigger, every single append would copy everything: n appends would cost 1+2+...+n = O(n²).

Because: a constant increment means a resize on every append, each costing O(current size)

Premise: Instead the list over-allocates proportionally — new capacity grows by a factor of the current size, so each resize buys a number of free appends proportional to the work it just did.

Because: only geometric growth makes the free appends grow as fast as the copy cost

Premise: With doubling, total copying is bounded by n + n/2 + n/4 + ... < 2n. Other fixed proportional growth factors change the constant, not the O(n) total. CPython does not literally double capacity; the amortised conclusion still applies.

Because: a geometric series with ratio below 1 sums to a constant multiple of its largest term

Conclusion: Therefore "O(1) amortised" is a precise claim about a sequence of operations, not about any single one. Any individual append may still stall for an O(n) copy.And note what this predicts, and this is the part that matters in production: amortised bounds say nothing about tail latency. In a latency-sensitive service the occasional resize is a visible spike, so allocating the final-sized result up front can help when its size is known; Python lists have no public reserve-capacity method. It also predicts why list.insert(0, x) stays O(n) forever — no growth strategy helps when every element must shift — and therefore why collections.deque exists.

Name: Contiguity versus hashing

Picture: Arrays and hash tables explain four central containers. CPython lists and tuples store contiguous references, not necessarily contiguous value objects; dicts and sets use hashing to locate entries. Counter and defaultdict specialize dict behavior, heapq maintains a heap in a list, and deque combines arrays with linked blocks. These representations trade lookup cost, movement, allocation and locality differently.

• Need position or order → array (list). Need identity lookup or dedup → hash (set/dict). Need both ends fast → deque. Need "smallest so far" repeatedly → heap.

• Repeated membership tests are candidates for a set or dict. Building a set costs expected O(n); there is no universal second-lookup break-even. Small lists, early hits and unhashable values can favor a scan.

• Hashability requires a stable hash and equal objects to have equal hashes. Lists are unhashable; tuples are hashable only if their elements are. A user-defined object can have mutable attributes yet retain the default identity-based equality and hash.

• Since 3.7 dicts preserve insertion order as a language guarantee, but they are still hash tables: order is a bonus, not the access mechanism.

Trigger: Fire this model the moment you see: a nested loop doing membership tests · if x not in results against a list · code that sorts inside a loop · TypeError: unhashable type · a job that ran in seconds on sample data and hours on the full set.

Decision: You must deduplicate and join two large collections of records in memory. Sort both and merge, or hash one and probe it?

Name: Hash join (build a dict/set from one side)

Gain: Expected O(n + m + r) time for a conventional equijoin with bounded-cost keys, where r is the number of output rows. A key-to-list mapping preserves multiple matching rows; a plain key-to-record dict would lose duplicates.

Cost: O(n) build-side storage plus any materialized output. Output order depends on the implementation; Python dicts preserve insertion order, but key-sorted join output requires an explicit policy. An in-memory implementation needs enough RAM.

Pick: the build side fits comfortably in RAM and equality matching is the task. Building the smaller side often helps, but join semantics, indexes and output order also constrain the choice.

Name: Sort-merge

Gain: Sorting both inputs costs O(n log n + m log m) in the comparison model; merging costs O(n + m + r). Already sorted inputs avoid that sorting work. Sequential reads can suit disk-backed data.

Cost: Sorting/storage costs depend on the algorithm, and Python's adaptive sort can exploit existing runs. Duplicate-key groups may need buffering or rescanning to emit all matches.

Pick: sorted input/output is valuable or an external-sort implementation suits the data. Database hash joins can also partition and spill; neither strategy is universally the only out-of-memory option.

Name: Keep it in the database / engine

Gain: the planner can use table statistics and indexes and keep intermediates out of your Python process, though the engine itself may materialize or spill them

Cost: a round trip, less control, and query cost you may be billed for

Pick: the data already lives in a table and pulling it into Python is only to do work SQL could express — almost always true for joins and aggregations

Verdict: Compare join semantics, ordering, cardinality and memory before choosing; use the smaller build side when the join permits it. The senior instinct is to estimate before choosing: rows × bytes-per-row against available RAM, remembering that Python objects carry substantial per-object overhead, so a "small" list of a few million dicts is not small.And the meta-answer: if you are hand-writing a join in Python over data that came from a database, the real tradeoff you should be evaluating is whether this belongs in Python at all.

(c) Hands-on · 25 min

Save as s008_data_structures.py, run.

"""s008_data_structures.py — the built-in menu, in action."""
from __future__ import annotations
from collections import Counter, defaultdict, deque, namedtuple, ChainMap
import time
 
# =========================
# Part 1 · O(n) list search vs O(1) set search
# =========================
print("--- Part 1 · perf ---")
 
N = 100_000
big_list = list(range(N))
big_set = set(big_list)
probe = N - 1                              # worst case for the list
 
t = time.perf_counter()
for _ in range(1000):
    _ = probe in big_list
list_ms = (time.perf_counter() - t) * 1000
 
t = time.perf_counter()
for _ in range(1000):
    _ = probe in big_set
set_ms = (time.perf_counter() - t) * 1000
 
print(f"list  1000 checks: {list_ms:.1f} ms")
print(f"set   1000 checks: {set_ms:.3f} ms")
print(f"set is ~{list_ms/set_ms:.0f}× faster for membership")
 
# =========================
# Part 2 · Counter — tally in one line
# =========================
print("\n--- Part 2 · Counter ---")
 
sentence = "the quick brown fox jumps over the lazy dog the fox is quick"
word_counts = Counter(sentence.split())
print(word_counts.most_common(3))
 
# Multiset math for free
bag_a = Counter("aabbc")
bag_b = Counter("abcd")
print("intersect:", bag_a & bag_b)   # min of each
print("sum:      ", bag_a + bag_b)   # add counts
print("diff:     ", bag_a - bag_b)   # subtract (min 0)
 
# =========================
# Part 3 · defaultdict — grouping without KeyError
# =========================
print("\n--- Part 3 · defaultdict ---")
 
rows = [("engineer", "ada"), ("engineer", "linus"), ("cook", "julia"), ("engineer", "grace")]
 
# BAD — verbose
groups_bad: dict[str, list[str]] = {}
for role, name in rows:
    if role not in groups_bad:
        groups_bad[role] = []
    groups_bad[role].append(name)
 
# GOOD — defaultdict does the ‘if missing’ for you
groups: dict[str, list[str]] = defaultdict(list)
for role, name in rows:
    groups[role].append(name)
 
print(dict(groups))
 
# =========================
# Part 4 · deque — O(1) at both ends
# =========================
print("\n--- Part 4 · deque ---")
 
# BFS queue — a canonical use
def bfs_levels(root: dict, children_key: str = "children") -> list[list]:
    queue = deque([(root, 0)])
    levels: dict[int, list] = defaultdict(list)
    while queue:
        node, level = queue.popleft()               # O(1) — list.pop(0) is O(n)
        levels[level].append(node["name"])
        for child in node.get(children_key, []):
            queue.append((child, level + 1))
    return [levels[i] for i in sorted(levels)]
 
tree = {
    "name": "root",
    "children": [
        {"name": "a", "children": [{"name": "a1"}, {"name": "a2"}]},
        {"name": "b", "children": [{"name": "b1"}]},
    ],
}
print(bfs_levels(tree))
 
# Ring buffer — the last N events, in constant memory
recent = deque(maxlen=5)
for i in range(20):
    recent.append(i)
print("last 5:", list(recent))
 
# =========================
# Part 5 · namedtuple — tiny records
# =========================
print("\n--- Part 5 · namedtuple ---")
 
Point = namedtuple("Point", "x y")
p = Point(3, 4)
print(p, p.x, p.y)
print("as dict:", p._asdict())
print("with replacement:", p._replace(y=99))
# Note: namedtuples with hashable fields can be dict keys or set elements.
seen: set[Point] = {Point(0, 0), Point(1, 1), Point(0, 0)}
print("unique points:", seen)
 
# For anything larger than 3 fields, prefer @dataclass (S014).
 
# =========================
# Part 6 · ChainMap — layered config
# =========================
print("\n--- Part 6 · ChainMap ---")
 
cli   = {"log_level": "DEBUG"}
env   = {"log_level": "INFO", "port": 8080}
defaults = {"log_level": "WARNING", "port": 80, "workers": 4}
 
config = ChainMap(cli, env, defaults)                # left-most wins
print("log_level:", config["log_level"])              # DEBUG (from cli)
print("port     :", config["port"])                   # 8080 (env, since cli lacks it)
print("workers  :", config["workers"])                # 4    (defaults)
 
# =========================
# Part 7 · Sets and set algebra
# =========================
print("\n--- Part 7 · set algebra ---")
 
writers = {"ada", "linus", "grace"}
speakers = {"grace", "hopper", "guido"}
 
print("both:      ", writers & speakers)
print("either:    ", writers | speakers)
print("writers only:", writers - speakers)
print("xor:       ", writers ^ speakers)
 
# Dedup while preserving order (3.7+ dicts are ordered)
def dedup(items):
    return list(dict.fromkeys(items))
print("dedup:", dedup([3, 1, 4, 1, 5, 9, 2, 6, 5, 3]))
 
# =========================
# Part 8 · When you need immutability — frozenset
# =========================
print("\n--- Part 8 · frozenset ---")
 
flag_sets = {
    frozenset({"admin", "read"}): "admin-role",
    frozenset({"read"}):          "reader-role",
}
print(flag_sets[frozenset({"read", "admin"})])   # order-independent lookup
# A regular set can't be a dict key: TypeError: unhashable type: 'set'

What each block teaches

Anatomy of the exercises

Name: Part 1 · perf reality

Desc: The script times 1000 late-hit lookups after constructing both containers. Its printed ratio is a local observation, not a benchmark of construction, memory, other hit positions or every Python workload.

Name: Part 2 · Counter

Desc: One-line tally + free multiset algebra (+, -, &, |). The right tool for word counts, histograms, most-frequent-item.

Name: Part 3 · defaultdict

Desc: Replaces the ubiquitous if key not in d: d\[key] = \[] pattern. defaultdict(int), defaultdict(set), defaultdict(list) are the three you'll use most.

Name: Part 4 · deque

Desc: Approximately O(1) at both ends. Useful for BFS and rolling buffers. Repeatedly draining a list with pop(0) takes quadratic work. A bounded deque discards items; use a synchronized queue when blocking or task coordination is required. Moving an arbitrary deque item is not O(1) LRU access.

Name: Part 5 · namedtuple

Desc: Tuple-style record with fixed fields, hashable only if all fields are hashable. Choose a dataclass when defaults, methods or other record behavior are useful; field count alone is not a correctness rule.

Name: Part 6 · ChainMap

Desc: Layered lookup for config precedence (CLI > env > file > defaults). Assignments and deletions through the ChainMap affect its first map; changes made directly to any underlying map remain visible.

Name: Part 7 · set algebra

Desc: &, |, -, ^ are the four set operators you should know. Perfect for ‘users who did A but not B’ type queries.

Name: Part 8 · frozenset

Desc: Immutable built-in set, hashable and usable as a dict key or another set's element. Its elements must themselves be hashable.

What to observe

ClassName: ml-4 list-decimal space-y-1

Part 1 prints the ratio for this particular late-hit workload; repeat measurements and include construction cost for your actual use case. Part 3's defaultdict version is 2 lines vs 5. Read reviewers prefer the shorter form because it's a common idiom. Part 4's deque popleft is O(1); the same code with a list pop(0) on a large list is quadratic. Part 7's dict.fromkeys trick dedups while preserving insertion order — a Python 3.7+ idiom worth memorising.

Goal: Solve a real practice problems with the right tool

Hint: Count n inputs in expected O(n), then select k from u unique keys in O(u log k) for the bounded-heap approach when 1 < k < u. Counting needs O(u) memory; requesting all results can instead involve sorting. Compare the same k and tie policy.

Given a stream of ~1M strings, return the top 10 most frequent. Constraints:

1. Solve with Counter.most_common(10) — the natural Python one-liner.
2. Solve with heapq.nlargest(10, counts.items(), key=lambda x: x[1]) — the same in HOF style.
3. Time both on 1M random 4-letter strings. Which is faster and why?

Bonus: what if the stream is a generator you can only iterate once? (Answer: same code — Counter accepts any iterable and reads it once.)

(d) Production reality · 15 min

Where this shows up in the rest of the plan

Root: Data-structure choice ripples through every future session

Label: S014 · Dataclasses & typing

Desc: Dataclasses offer a different record API; mutability, equality, hashing and slots are choices, not automatic equivalents of namedtuple.

Label: S015 · Big-O

Desc: The formal treatment of what today was hand-wavy. Same lesson, deeper.

Label: S023 · Arrays & strings

Desc: Lists and tuples are sequences; str is an immutable Unicode text sequence, not a Python list. Their storage and operation costs differ.

Label: S024 · Hashmaps

Desc: Dict internals — hash function, open addressing, load factor. You'll understand WHY dict is O(1).

Label: S045 · Pandas / Polars

Desc: A DataFrame exposes named columns. Join and grouping concepts carry over, but columnar engines use their own typed storage and execution algorithms.

Label: S089 · Caching

Desc: OrderedDict can implement exact LRU order with move_to_end. Redis offers several data types and eviction policies; its approximate LRU is not this Python implementation.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click each to reveal

Q: You need to check membership on the same collection 10,000 times. List or set?

A: Usually a set for a large collection of hashable values: expected O(n) construction and O(1) per lookup versus O(n) worst-case list membership. Measure small collections and account for the extra storage.

Q: When would you use a tuple instead of a list?

A: When the collection has a fixed shape and shouldn't change (function returning multiple values, coordinate pair, dict key). Tuples have fixed element references and are hashable only if all elements are hashable. CPython tuples often have less container overhead than comparable lists.

Q: What's defaultdict(list) and why is it better than a plain dict for grouping?

A: A dict subclass that auto-creates missing values by calling the factory. d[k].append(x) works without KeyError, replacing the ‘if key not in d: d[key] = []’ pattern. Half the code, same behaviour.

Q: Why is list.pop(0) slow, and what's the alternative?

A: O(n): later list elements shift left one position. Use collections.deque for O(1) popleft(); CPython stores its elements in linked fixed-length blocks. A bounded deque can provide a rolling-buffer interface without being implemented as a circular linked list.

Q: Given Counter('abracadabra'), what does .most\_common(2) return?

A: [('a', 5), ('b', 2)]

Q: Can a set be a dict key? Can a frozenset?

A: Set: NO — mutable, unhashable. frozenset: YES — immutable, hashable. A tuple is a key only when every element is hashable; immutability alone is not the general definition of hashability.

Q: What's the memory difference between list(range(1\_000\_000)) and set(range(1\_000\_000))?

A: Separate the container from its referenced integers. On a typical 64-bit CPython build the list's million references alone occupy about 8 MB; a set table needs more spare slots and stored hashes. Both also retain integer objects. Use sys.getsizeof(container) for shallow size, then account for uniquely owned referents without double-counting shared objects. Interpreter, allocation history and payloads determine the total; no universal 3–4× whole-object ratio follows. For a million-entry dict, count both key and value references, the hash/index table and any separately owned keys/values. On a 64-bit reference model, just a million key/value reference pairs represent roughly 16 MB before table capacity, hashes and object overhead, versus roughly 8 MB for a million list references. This is a lower-level accounting estimate, not a whole-dict measurement; shared objects must only be counted once.

Q: Fix this: for k, v in d.items(): if v is None: del d\[k].

A: for k in list(d): ... or d = {k: v for k, v in d.items() if v is not None}. Adding or deleting dictionary entries during iteration may raise RuntimeError or miss entries. Updating an existing value is different from changing the key set.

Q: You have a config: CLI flags override env vars override defaults. Which stdlib type gives you this in one line?

A: collections.ChainMap(cli, env, defaults) — search order is left-to-right. Lookups probe up to k maps, expected O(k) under ordinary dict hashing assumptions.

Q: Stretch — you have 100M events, each with user\_id, timestamp, action. You want: unique users, top-10 actions, and per-user last event, in one streaming pass. Which structures do you use and why?

Stretch: true

A: Use a Counter for action counts and a dict from user ID to retained event. Its keys already give unique users, so a separate set is optional. For latest-by-timestamp, replace an event only when the new timestamp is greater; define a tie policy (for example, keep the first arrival). Unconditional assignment keeps the last arrival, which is only the latest event if arrival order is guaranteed. Memory is O(u + a) entries for u users and a distinct actions, plus retained payload sizes; millions of Python event objects can require substantial RAM, so measure rather than assume a few hundred MB.

Explain-out-loud test

If you can't teach these three without notes, redo the session:

1. When do you use a set instead of a list? (one rule)
2. What's defaultdict(list) for? (one concrete example)
3. Why is deque better than list for a queue? (Big-O both ends)

What comes next

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

• collections — Container datatypes — Python 3.14.8 documentation — Counter equality in Python 3.10+ treats missing keys as zero counts. Checked 2026-10-07.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.