Choosing the Right Data Structure
Pick containers by how you read, update, and traverse data - not by habit. The wrong structure costs clarity and asymptotic performance; the right one makes code shorter and faster without micro-optimizing.
Recipe
Ask four questions before coding:
- Do I need fast membership by value or key?
- Must order be preserved or sortable?
- Are duplicates allowed?
- Is data tabular (millions of rows, column ops)?
Map answers to dict, set, list, deque, heapq, or dataframe libraries.
When to reach for this:
- Designing a new module's in-memory model
- Refactoring nested lists into clearer structures
- Performance reviews showing O(n) scans in hot paths
- Architecture discussions before persistence choice
Working Example
from collections import defaultdict, deque
import heapq
# Pattern: index users by id -> dict
users_by_id: dict[int, dict] = {1: {"name": "Ada"}, 2: {"name": "Linus"}}
# Pattern: dedupe tags -> set
tags = set(["py", "ml", "py"])
# Pattern: FIFO job queue -> deque
jobs: deque[str] = deque(["a", "b"])
# Pattern: priority scheduling -> heapq
heap: list[tuple[int, str]] = []
heapq.heappush(heap, (2, "low"))
heapq.heappush(heap, (1, "high"))
# Pattern: group rows -> defaultdict
by_role: defaultdict[str, list[str]] = defaultdict(list)
for name, role in [("Ada", "admin"), ("Linus", "dev")]:
by_role[role].append(name)What this demonstrates:
- Dict for keyed lookup
- Set for uniqueness and membership
- Deque for FIFO without
pop(0)penalty - Heap for priority ordering
- defaultdict for group-by without boilerplate
Deep Dive
Decision Table
| Access pattern | Prefer | Why |
|---|---|---|
| Lookup by unique key | dict | O(1) average |
| Membership test | set | O(1) average |
| Ordered append + scan | list | Simple, cache-friendly |
| Queue/stack both ends | deque | O(1) pops |
| Top-K / schedule | heapq | O(log n) updates |
| Columnar analytics | pandas/polars | Vectorized ops |
How It Works
- Asymptotics matter at scale - O(n) scans hurt at 10^6 items, fine at 50.
- Constants matter at small n - Dict overhead can lose to list scan for tiny collections.
- Immutability signals intent - Tuple/frozenset document stability and enable hashing.
- Composition beats one-size - Graph as
dict[node, set[neighbor]]combines dict + set. - Persistence boundary - In-memory choice differs from SQL/Redis decision.
Python Notes
# smell: repeated linear search
if item in big_list: # O(n) each time
# fix: build set once
seen = set(big_list)
if item in seen: # O(1) averageGotchas
- list as set -
if x in itemson large list in loop → O(n²). Fix: Prebuildset(items). - dict when list of pairs suffices - Two-item records sometimes better as tuples in list. Fix: Simplify until keyed lookup needed.
- pandas for 20 rows - Heavy import and API overhead. Fix: Plain dict/list until hundreds+ rows or column ops.
- OrderedDict by default - Unnecessary since dict ordered. Fix: Plain dict unless
move_to_end. - Premature heap - Five items sorted once →
sorted. Fix: heap when k << n or streaming.
Alternatives
| Alternative | Use When | Don't Use When |
|---|---|---|
| SQLite in-memory | Relational queries on moderate data | Simple counter |
| Redis | Shared cache across processes | Single-process script |
| ORM models | Persistent domain entities | Ephemeral algorithmic buffer |
slots classes | Many small fixed-field objects | Dynamic JSON blobs |
FAQs
list or deque for stack?
list.append/pop is fine for stack-only. Use deque when popping from left or both ends.
When pandas over dict of lists?
Column-wise stats, joins, filtering on millions of rows - not for 30-key config dict.
tuple or dataclass?
Tuple/NamedTuple for small immutable bundles. dataclass when defaults, methods, or mutability needed.
dict key: str or int?
Pick natural domain key. Int ids faster and smaller than stringified ids when numeric.
How to model graph?
dict[node, list[neighbor]] or defaultdict(set) for sparse graphs. NetworkX for algorithms library.
Counter vs dict for counts?
Counter when doing multiset math or most_common. Plain dict fine for single-pass tally.
bisect or heap?
bisect for mostly sorted insertions; heap for dynamic min/max extraction.
When immutability?
Dict keys, set elements, hash caches, shared read-only config - tuple/frozenset/bytes.
Does order matter for set?
No semantic order - if display order matters, use list or OrderedDict pattern with dict.fromkeys.
How to document choice?
One-line comment or ADR when non-obvious - future readers inherit context.
Related
- Data Structures Basics - Big-O overview
- collections Module - specialized containers
- Immutability & Hashability - key constraints
- heapq & Priority Queues - scheduling
Stack versions: This page was written for Python 3.14.0 (stable 3.14, maintenance 3.13), FastAPI 0.115+, Django 5.2, Flask 3.1, Pydantic 2, PyTorch 2.6+, pandas 2.2+, Polars 1.x, ruff 0.9+, and uv 0.6+.