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

Module M01: Python Foundations · Session 8 of 130 · Track: SW 📦

What you'll be able to do after this session

• Explain Data Structures to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S007 — Functions — arguments, scope, closures

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Python Data Structures — Programming with Mosh (excerpt) — Rapid tour of list/tuple/dict/set with typical operations.
• 🎥 Deep dive (30–60 min) · Raymond Hettinger — Transforming Code into Beautiful, Idiomatic Python (PyCon) — The canonical talk. Half of it is picking the right data structure.
• 🎥 Hands-on demo (10–20 min) · collections module — Corey Schafer — Counter, defaultdict, namedtuple, deque — the four collections you'll use weekly.
• 📖 Canonical article · Python Docs — Data Structures (§5) — The official tutorial covering list, tuple, dict, set methods.
• 📖 Book chapter / tutorial · Fluent Python (2e) — Chapter 3: Dictionaries and Sets (excerpt) — Deep dive on how dict is implemented, why lookups are O(1).
• 📖 Engineering blog · Instagram Engineering — Dismissing Python Garbage Collection at Instagram — Real story of tuning Python's memory model at scale — starts with data-structure choice.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: Pick the right container and your code writes itself.

Choosing the right data structure is often the difference between a 3-second script and a 3-hour one. Python gives you four core collections (list, tuple, dict, set) and a handful of specialised ones (deque, Counter, defaultdict, namedtuple, heapq). Once you internalise which one fits which shape of problem, half of the programming battle is won.

Think of it like kitchen containers. A list is a shopping bag: ordered, you can add and remove items, but finding "do I have milk?" means opening the bag and looking through everything (O(n)). A set is a labelled drawer: instant "do I have milk?" (O(1)) but no ordering. A dict is a filing cabinet: for each label (key), one folder (value), O(1) lookup. A tuple is a sealed envelope: fixed contents, cheap, hashable — so it can be a dict key.

The single most useful rule: whenever you find yourself writing if x in some_list, ask "should this be a set or dict?" Membership checks on lists are O(n); on sets/dicts they're O(1). One-line change, 1000× speedup on big data.

Gotcha to carry forever: dicts have preserved insertion order since Python 3.7, but sets do NOT guarantee any order — never rely on set iteration order. And when you use a list as a dict key, Python throws TypeError: unhashable type: 'list' — use a tuple instead, because tuples are immutable and therefore hashable.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

The Big-O cheat sheet for the four built-in collections (the two operations you'll ask about most):

The decision tree — which collection do I need?

Worked example — pick the container, watch it change everything:

# Task: given a large list of user IDs, and a stream of queries, answer "is this ID present?"
 
# Naive (list) — O(n) per query, O(n·q) total
users = [1, 5, 42, 99, ...]          # 1M items
for q in queries:                     # 100k queries
    if q in users: ...                 # O(1M) each → 10^11 operations
 
# Smart (set) — O(1) per query, O(n + q) total
users_set = set(users)                # O(n) once
for q in queries:
    if q in users_set: ...             # O(1) each → 10^5 operations

For 1M items and 100 k queries, that's a factor of ~10⁶ speed-up. This isn't hypothetical — it's the single most common "why is my Python slow?" fix.

The collections module — memorise these four:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

Run through each block. Predict output before hitting enter.

# s008_data_structures.py
from collections import Counter, defaultdict, deque, namedtuple
 
# 1. list — ordered, mutable, O(n) membership.
nums = [3, 1, 4, 1, 5, 9]
nums.append(2); nums.remove(1); nums.sort()
print(nums, 5 in nums)
 
# 2. tuple — ordered, immutable, hashable, cheap.
point = (10, 20)
# point[0] = 99  # would raise TypeError
by_point = {point: "origin"}
print(by_point)
 
# 3. dict — O(1) key→value lookup.
prices = {"apple": 50, "banana": 20, "cherry": 300}
prices["date"] = 80
print(prices.get("mango", "n/a"))   # safe lookup with default
for k, v in prices.items():
    print(k, v)
 
# 4. set — O(1) membership, no duplicates.
tags_a = {"python", "backend", "sql"}
tags_b = {"sql", "spark", "python"}
print("intersection:", tags_a & tags_b)
print("union:",        tags_a | tags_b)
print("only in a:",    tags_a - tags_b)
 
# 5. The killer speedup — list vs set for `in`.
import time, random
big = list(range(1_000_000))
big_set = set(big)
targets = [random.randint(0, 2_000_000) for _ in range(10_000)]
 
t0 = time.perf_counter()
sum(1 for t in targets if t in big)
print("list  :", round(time.perf_counter()-t0, 3), "s")
 
t0 = time.perf_counter()
sum(1 for t in targets if t in big_set)
print("set   :", round(time.perf_counter()-t0, 4), "s")
 
# 6. Counter — count anything.
text = "the quick brown fox jumps over the lazy dog the fox is quick"
print(Counter(text.split()).most_common(3))
 
# 7. defaultdict — group things.
pairs = [("fruit","apple"), ("veg","carrot"), ("fruit","banana"), ("veg","kale")]
groups = defaultdict(list)
for k, v in pairs:
    groups[k].append(v)
print(dict(groups))
 
# 8. deque — bounded sliding window.
last3 = deque(maxlen=3)
for x in [10, 20, 30, 40, 50]:
    last3.append(x)
    print(list(last3))
 
# 9. namedtuple — a tuple with names (often replaced by @dataclass in modern code).
User = namedtuple("User", "id name email")
u = User(1, "dinesh", "d@example.com")
print(u.name, u[1])   # both work
 
# 10. dict/set comprehensions.
squared = {n: n*n for n in range(5)}
uniques  = {c for c in "abracadabra"}
print(squared, uniques)

Checklist — what to observe:

1. Step 2: mutating a tuple raises; using it as a dict key works.
2. Step 3: dict.get(key, default) is far cleaner than if key in d: ... else: ....
3. Step 5: expect the set lookup to be ~1000× faster than the list lookup.
4. Step 6: Counter.most_common(k) is the one-liner for top-k frequency questions.
5. Step 7: defaultdict(list) removes 3 lines of guard code per group operation.

Try this modification: re-run Step 5 with big = list(range(10_000_000)) and targets of length 100 000. The list version will take tens of seconds; the set version will still finish in under a second. This is the moment where "picking the right container" becomes a career skill.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

War story — the O(n) in on a big list. A data pipeline at Uber deduped 5 M rows with if row not in seen: seen.append(row) where seen was a list. The job took 3 hours. Switching seen to a set cut it to 20 seconds. Every senior reviewer looks for x in some_list in hot loops.

War story — the wrong container for a queue. A background worker used list.pop(0) to consume tasks — that's O(n) because every remaining element shifts left. Under load, latency ballooned. collections.deque (O(1) popleft) fixed it in a one-line change. This exact pattern is in the Python docs' deque motivation.

War story — insertion-order surprise. A team relied on set iteration order for a cache eviction policy. It worked in dev, failed intermittently in prod on a different Python build. Lesson: dict preserves insertion order (guaranteed since 3.7); set does NOT. Use dict (values None) or collections.OrderedDict if you need order + uniqueness.

How top teams choose containers:

• set for membership, dict for lookup, list for ordered sequences you actually iterate, tuple for fixed records.
• collections.Counter replaces 4 lines of hand-rolled count-by-key code. Used everywhere from NLP pipelines to metrics aggregation.
• collections.defaultdict(list) replaces the if key not in d: d[key] = [] boilerplate. Half of the groupby-style code in Python is this pattern.
• collections.deque(maxlen=N) for bounded sliding windows — network rate limiters, moving averages, streaming stats.
• heapq (a plain list used as a binary heap) for priority queues — Session S029 covers heaps end-to-end.
• frozenset when you need a hashable set (e.g. as a dict key or in another set).

Perf notes:

• list.append is O(1) amortised; list.insert(0, x) and list.pop(0) are O(n).
• dict/set in is O(1) average, worst-case O(n) if hash collisions cluster (rare in practice, but the reason security-sensitive code uses randomised hash seeds — Python does this by default).
• Comprehensions ([f(x) for x in xs]) are ~30 % faster than the equivalent explicit for + append loop in CPython 3.12.
• If your bottleneck is a Python-level loop over millions of numbers, the answer is NumPy, not a smarter container.

The habit that will save you: every time you write in some_list in a hot loop, pause and ask "should this be a set?" Every time you write for k in d: … d[k] …, pause and ask "should this be d.items()?" These two questions eliminate half of the first-year performance bugs.

(e) Quiz + exercise · 10 min

1. What is the Big-O of x in some_list vs x in some_set? Why?
2. Why can you use a tuple as a dict key but not a list?
3. Name a case where collections.deque beats list, and explain why.
4. What's the difference between dict.get(k) and dict[k] when k is missing?
5. Counter("abracadabra").most_common(2) → what does it return, and what's the Big-O?

Stretch problem (connects to S006/S007): given a list of dicts orders = [{"customer": "A", "amount": 100}, {"customer": "B", "amount": 40}, {"customer": "A", "amount": 60}], write a one-line comprehension + defaultdict (or Counter) that produces {"A": 160, "B": 40}. Compare against writing it with a plain for loop — which is easier to read?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Data Structures? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S009): Classes & Objects — the OOP Mental Model
• Previous (S007): Functions — arguments, scope, closures
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.