Data Structures

Python’s built-in collections

Python ships four general-purpose container types in the language core — no imports required.

Type	Syntax	Mutable	Ordered	Duplicates	Hashable
`list`	`[1, 2, 3]`	yes	yes	yes	no
`tuple`	`(1, 2, 3)`	no	yes	yes	only if every element is
`dict`	`{"a": 1}`	yes	yes (3.7+)	keys: no	no
`set`	`{1, 2, 3}`	yes	no	no	no
`frozenset`	`frozenset({1, 2})`	no	no	no	yes

Each type has a distinct strength: lists for ordered sequences, tuples for fixed records, dicts for key-value lookup, and sets for membership tests and set algebra. frozenset is the immutable sibling of set — trading mutation for the ability to be a dict key or live inside another set.

Mutable and hashable are opposites. Every mutable type here (list, dict, set) is unhashable — its value could change after being used as a key, which would corrupt whatever hashed it. tuple is hashable only conditionally: hashable if and only if every element it holds is itself hashable, because a tuple holding a mutable element (like a list) inherits that element’s instability.

Choosing the right collection

Reach for a list when you need to append, sort, or index items by position.
Use a tuple when the data is fixed and positional meaning matters (e.g., an RGB colour, a database row).
Use a dict when you need fast key-based lookup or want to group named attributes without defining a class.
Use a set when uniqueness is the primary concern or you need union / intersection / difference operations.

Runnable overview

Open in an online REPL

# --- list ---
nums = [1, 2, 3, 4, 5]
print('list:', nums)
print('sum:', sum(nums))

# --- tuple unpacking ---
coords = (10, 20, 30)
x, y, z = coords
print('tuple unpack:', x, y, z)

# --- dict (insertion order preserved since Python 3.7) ---
scores = {'alice': 95, 'bob': 87, 'carol': 92}
print('dict:', scores)
print('alice score:', scores['alice'])

# --- set (duplicates removed automatically) ---
unique = {3, 1, 4, 1, 5, 9, 2, 6, 5}
print('set:', sorted(unique))

# --- hashability decides what can be a dict key or set member ---
by_coords = {coords: 'a point'}   # tuple works: it's hashable
print('tuple as dict key:', by_coords)

try:
    by_list = {nums: 'broken'}    # list does not: it's mutable, unhashable
except TypeError as e:
    print('TypeError:', e)

Mental Model

list      [ 1 | 2 | 3 ]   mutable, ordered      -- reorder/replace freely
tuple     ( 1 | 2 | 3 )   immutable, ordered     -- fixed once built
dict      { k: v, ... }   mutable, ordered keys  -- lookup by hash(key)
set       { 1, 2, 3 }     mutable, unordered     -- membership by hash(value)
frozenset immutable set                          -- hashable, unlike set

hashable  = can compute a stable hash() -> usable as a dict key / set member
mutable   = value can change after creation without changing identity
these two are opposites: every built-in mutable type here is unhashable

Trade-offs

What you get	Benefit	Cost
`list`	ordered, mutable, indexable by position	`O(n)` membership test (`in`); `O(n)` insert/remove anywhere but the end
`tuple`	immutable, lightweight, hashable if its elements are	can’t grow, shrink, or reorder after creation
`dict`	`O(1)` average key lookup, preserves insertion order	every key must be hashable
`set` / `frozenset`	`O(1)` average membership test, deduplicates for free	unordered — no indexing, no guaranteed iteration order; `set` itself can’t be a dict key (only `frozenset` can)

Common Misconceptions

“{} creates an empty set” — fact: {} creates an empty dict. The only way to create an empty set is set().
“All four collections support the same operations” — fact: only list and dict support assigning into an existing position (lst[0] = x, d[k] = v); tuple, set, and frozenset never support item assignment.
“Picking a collection type is a style choice” — fact: it changes the complexity class of your operations (O(1) vs O(n) lookup) and the mutability guarantees callers can rely on — this is a correctness and performance decision, not a style one.
“A tuple is always hashable because tuples are immutable” — fact: only if every element inside it is also hashable; a tuple holding a list is not hashable.

Reading AI-generated code

Does the code write seen = {} and then call .add(...) on it? {} is a dict, not a set — .add does not exist on dict, and this raises AttributeError the first time it runs.
Does a loop do repeated x in some_collection checks against something that started life as a list and keeps growing? That’s an O(n) check on every iteration; a set makes the same check O(1) on average.
Is a tuple treated as if it supports .append() or item assignment “just this once”? Both raise immediately — AttributeError or TypeError.
Does code assume a set’s iteration order is meaningful or reproducible? It isn’t — only list, tuple, and dict (3.7+) give ordering guarantees.

🐛 Spot the bug

def unique_ids(records):
  seen = {}
  result = []
  for record in records:
      if record['id'] not in seen:
          seen.add(record['id'])
          result.append(record)
  return result


print(unique_ids([{'id': 1}, {'id': 2}, {'id': 1}]))

Show the answer

seen = {} creates an empty dict, not a set — {} is always a dict literal in Python; the empty-set spelling is set(). record['id'] not in seen still works (checking membership against a dict checks its keys), but seen.add(record['id']) fails immediately, because dict has no .add method — only set does. Verified on Python 3.14: AttributeError: 'dict' object has no attribute 'add'. The fix is seen = set().