Data Structures: Lists and Dicts
Ordered sequences and hash maps
Lists are ordered mutable sequences and dicts are O(1) key→value maps — the two structures nearly every data pipeline is built from; understanding their costs and semantics is core Python literacy.
What you will learn
- Choose list vs set vs dict for a job
- Use dict methods: get, setdefault, defaultdict, Counter
- Predict the big-O of common ops
What is this?
Lists preserve order and support indexing, slicing, append, and O(n) lookup by value. Dicts map hashable keys to values with average O(1) lookup. Sets are dicts without values — O(1) membership. Knowing which structure fits a job changes pipeline performance by orders of magnitude.
Why do you need it?
- Dict lookup is the single biggest performance win available in pure Python.
- collections.Counter turns 'count everything' into one line.
- Pandas indexes are dict-like internally; the mental model ports over.
- JSON, rows and config — the primary data shapes — are literally lists of dicts.
Mental model
A stack of papers vs a filing cabinet with labeled drawers
List vs dict
Finding a paper in the stack takes scanning (O(n)); the cabinet jumps straight to the drawer's key (O(1)). Perfectly sorted cabinets need extra maintenance — just like sorted lists.
How it works
- Lists: contiguous slots; `lst.append` amortized O(1); `x in lst` O(n); slicing returns a new list.
- Dicts: hash the key → slot; lookup average O(1); insertion ordered in modern Python.
- `d.get(k, default)` avoids KeyError; `d.setdefault(k, v)` seeds missing keys.
- collections.defaultdict(list)` auto-creates empty lists on first touch.
- collections.Counter(dict subclass) counts hashables: `Counter(words).most_common(10)`.
Choosing a structure.
Examples
The data-science dict toolkit
from collections import defaultdict, Counter events = ["buy", "view", "buy", "view", "buy"]count = Counter(events)print(count.most_common()) # [('buy',3),('view',2)] user_items = defaultdict(list)user_items["alice"].append("skirt") # auto-creates the listprint(user_items) # {'alice': ['skirt']} # Fast membership: set beats list for vuet checksids = {1, 2, 3}print(2 in ids, 9 in ids) # True FalseCounter is a dict subclass counting hashables; defaultdict supplies missing keys on first access; sets give O(1) membership. These three patterns replace many hand-rolled loops.
In production
- A click-stream job uses Counter to aggregate top pages per hour without SQL.
- A deduplication step maintains a set of seen IDs so a 10M-row stream stays O(1) per check.
- Feature lookups run through dicts keyed by user_id — those microsecond differences add up at 10k req/s.
Best practices
- Build dicts with dict.get/setdefault rather than try/except KeyError when defaults are expected.
- Use Counter for tallying and defaultdict for group-and-collect.
- Prefer sets over lists whenever you only ever ask 'is it present?'.
Common mistakes
- Using `x in list` inside a hot loop (O(n) each) when a set would be O(1).
- Mutating a dict while iterating its keys — collect keys first, then delete.
- Using unhashable keys (lists) in a dict — use tuples.
Debugging tips
- For 'missing key' bugs, print the repr of the key — whitespace/type mismatches are the classics.
- If membership is slow, convert the list to a set and re-profile.
- Interning: strings from user input may not equal constant strings — normalize casing/stripping.
Interview checkpoint
Hands-on lab
- Aggregate rows with dict tools
- Deduplicate with sets
- Compare list-scan vs set membership speed
Lists, Dicts and Sets in Anger
25 min · beginner
Quick quiz
Which structure gives O(1) membership checks?
`Counter` counts hashables and provides `most_common()`.