Collection complexity (list / tuple / set / dict)

The gotcha

Picking the wrong container turns linear work into quadratic. The classic version: if x in some_list inside a loop over a million items. Use the right type, get O(N); use the wrong one, get O(N²).

Big-O cheat sheet

* append is amortized O(1) — occasional resize doubles capacity.

set and dict are O(1) average, O(n) worst-case under hash collisions. CPython’s hash randomization makes adversarial worst-case rare.

The in test — biggest perf trap

items = list(range(1_000_000))
for q in queries:                   # if queries has 1M elements
    if q in items:                  # O(n) per check → O(n²) total
        ...

# Fix: O(1) membership
items_set = set(items)              # one-time O(n)
for q in queries:
    if q in items_set:              # O(1)
        ...

Whenever you see if x in <list> inside a loop, stop and convert to a set.

Why tuple exists when list already does

Common interview question. The difference isn’t speed of access (both O(1)). It’s:

• Immutability — tuple is hashable, can be a dict key or set member.
• Memory — tuple is more compact: no over-allocation buffer (lists keep extra capacity for amortized append).
• Slightly faster construction — fewer fields to initialize, no growth bookkeeping. ~2× faster for small literals.

import sys
sys.getsizeof([1, 2, 3])    # 80 (list with growth buffer)
sys.getsizeof((1, 2, 3))    # 64 (tuple, exact size)

When data is fixed (struct-like records, function returns of multiple values), tuple wins on every dimension. When data is built up, list wins.

dict and set internals

Both use open-addressed hash tables. Key requirements:

• Keys/elements must be hashable — __hash__ returns int, __eq__ consistent with hash.
• Mutable types (list, dict, set) are not hashable; immutable types (str, int, tuple of immutables, frozenset) are.

Lookup: hash(key) & (table_size - 1) → bucket → linear probing on collision → compare with __eq__.

Average O(1), worst-case O(n) under pathological collisions. CPython resizes when load factor > 2/3.

See 32_dict_internals.md, 33_list_internals.md, 18_dict_hashable_objects.md, 23_eq_vs_hash.md.

deque — when neither end of a list is fast enough

from collections import deque

dq = deque([1, 2, 3])
dq.appendleft(0)        # O(1) — list would be O(n)
dq.popleft()            # O(1)
dq.rotate(1)            # O(k)

Use for queues, sliding windows, BFS. Not random-access friendly: dq[len(dq)//2] is O(n).

frozenset and immutable variants

frozenset is to set what tuple is to list: hashable, immutable. Use as dict key or set element when you need a “set of sets”:

seen = set()
for combo in combinations:
    seen.add(frozenset(combo))      # frozenset is hashable

OrderedDict — historical note

In Python 3.7+, regular dict preserves insertion order as a language guarantee. OrderedDict is now mostly redundant unless you need:

• move_to_end(key, last=True/False) — reorder
• Equality that compares order: OrderedDict([('a', 1), ('b', 2)]) != OrderedDict([('b', 2), ('a', 1)]) (regular dict considers them equal).

The “sorted by insertion” pattern

dict preserves insertion order. So:

counts = {}
for item in items:
    counts[item] = counts.get(item, 0) + 1
# iterating counts goes in first-seen order

vs. Counter which iterates in counted order with .most_common().

When to use which

• Look up by key / dedupe → dict / set.
• Ordered, mutable, mostly-append → list.
• Fixed record / returning multiple values / hashable composite → tuple.
• Both ends fast → deque.
• Set of sets / dict key from a set → frozenset.

Interview angle

• Q: “Big-O of x in list vs x in set?” — O(n) vs O(1).
• Q: “Why is tuple faster than list for fixed data?” — no over-allocation, smaller, hashable.
• Follow-up: “What’s the difference between dict and OrderedDict in Python 3.7+?” — dict preserves order; OrderedDict adds move_to_end and order-sensitive equality.
• Follow-up: “When does set insert become O(n)?” — under heavy hash collisions. Hash randomization makes this rare; pathological keys (custom __hash__ returning the same value) can trigger it.

See 32_dict_internals.md, 33_list_internals.md, 01_theory_foundations/02_big_o_notation.md, stdlib/01_collections.md.