Choosing the Right Structure

The right data structure turns an O(n²) algorithm into O(n). This page is a reference you can return to when in doubt.

Decision tree

Do you need key → value lookup?
  └─ Yes → dict
       ├─ Keys might be missing and you want a safe default? → defaultdict
       └─ You're counting occurrences? → Counter

Do you need ordered, changeable items?
  └─ Yes → list
       └─ Fast append/pop from the left too? → deque (with maxlen for sliding windows)

Do you need ordered, fixed items (won't change)?
  └─ Yes → tuple
       └─ Fields have names? → namedtuple  (or @dataclass if you need methods)

Do you need uniqueness / set algebra?
  └─ Yes → set
       └─ Must be hashable (e.g. dict key)? → frozenset

Complexity reference

Operation	list	deque	dict	set
Access by index [i]	O(1)	O(n)	O(1)	—
x in s	O(n)	O(n)	O(1)	O(1)
Append to end	O(1)	O(1)	—	—
Append to front	O(n)	O(1)	—	—
Insert middle	O(n)	O(n)	—	—
Delete by value	O(n)	O(n)	O(1)	O(1)
Iteration	O(n)	O(n)	O(n)	O(n)
Union / intersection	O(n²)	—	—	O(n)

Common anti-patterns

Using a list for membership tests in a hot loop

# Slow — O(n) per check, O(n²) total
valid = [10, 20, 30, 40, 50]
hits  = [x for x in big_list if x in valid]

# Fast — O(1) per check, O(n) total
valid = {10, 20, 30, 40, 50}
hits  = [x for x in big_list if x in valid]

Using list.pop(0) as a queue

# Slow — O(n) per pop
queue = [1, 2, 3, 4]
queue.pop(0)

# Fast — O(1) per popleft
from collections import deque
queue = deque([1, 2, 3, 4])
queue.popleft()

Manually tracking counts with a dict

# Verbose
counts = {}
for w in words:
    counts[w] = counts.get(w, 0) + 1

# Idiomatic
from collections import Counter
counts = Counter(words)

Summary

If you need…	Use
Ordered, mutable sequence	list
Fast front-and-back append/pop	deque
Ordered, immutable sequence	tuple
Immutable sequence with named fields	namedtuple
Key → value, any keys	dict
Key → value, missing keys safe	defaultdict
Counting occurrences	Counter
Unique items, O(1) membership	set
Unique items, must be hashable	frozenset