Data Structures
Appending at the end and popping from the end are cheap. Inserting or removing at the front (or anywhere but the end) is expensive because every subsequent element has to shift.
🎯 What you'll learn
- The Four Built-in Containers
- Lists — Dynamic Arrays
- Tuples — Immutable, Fixed-Size Sequences
- Dicts — Hash Maps with Insertion Order
- Sets — Unique Elements, Fast Membership
1The Four Built-in Containers
| Type | Ordered | Mutable | Duplicates | Indexed by |
|---|---|---|---|---|
list | Yes | Yes | Yes | integer position |
tuple | Yes | No | Yes | integer position |
dict | Yes (insertion) | Yes | keys unique | key (hashable) |
set | No (but stable per-run) | Yes | No | — (membership only) |
lst = [1, 2, 3]
tup = (1, 2, 3)
d = {"a": 1, "b": 2}
s = {1, 2, 3}2Lists — Dynamic Arrays
nums = [3, 1, 2]
nums.append(4) # O(1) amortized
nums.insert(0, 0) # O(n) — shifts every element right
nums.pop() # O(1) — removes/returns the LAST element
nums.pop(0) # O(n) — removes the FIRST element, shifts everything left
nums.sort() # O(n log n), in-place, stable (Timsort)
sorted(nums) # returns a NEW sorted list, leaves nums untouched
nums[1:3] # slicing returns a new list (shallow copy of that range)Appending at the end and popping from the end are cheap. Inserting or removing at the front (or anywhere but the end) is expensive because every subsequent element has to shift.
3Tuples — Immutable, Fixed-Size Sequences
point = (3, 4)
x, y = point # unpacking
point[0] = 5 # TypeError — tuples don't support item assignment
def min_max(values):
return min(values), max(values) # implicitly builds and returns a tuple
lo, hi = min_max([3, 1, 4, 1, 5])Tuples are commonly used for fixed-shape records (a coordinate, a database row, multiple return values) and as dict keys — since they're hashable (as long as every element inside is also hashable), unlike lists.
4Dicts — Hash Maps with Insertion Order
config = {"host": "localhost", "port": 8080}
config["port"] # 8080 — O(1) average lookup
config.get("timeout", 30) # 30 — default if key missing, doesn't raise
config.setdefault("retries", 3) # sets AND returns; no-op if key exists
for key, value in config.items():
print(key, value) # iterates in INSERTION order (guaranteed since 3.7)
config.pop("port") # removes and returns the value
"host" in config # O(1) average — key membership testdict[key] raises KeyError if the key is absent; .get() never raises.
5Sets — Unique Elements, Fast Membership
seen = {1, 2, 3}
seen.add(4)
seen.discard(99) # no error even if 99 isn't present (.remove() WOULD raise)
a = {1, 2, 3}
b = {2, 3, 4}
a | b # union: {1, 2, 3, 4}
a & b # intersection: {2, 3}
a - b # difference: {1}
a ^ b # symmetric difference: {1, 4}Sets are the right tool whenever the question is "is X present?" or "what's common/different between these groups?" — membership testing is O(1) average, versus O(n) for a list.
6Choosing the Right Structure
| Need | Use |
|---|---|
| Ordered, duplicates allowed, will change size | list |
| Fixed-shape record, or a hashable dict key | tuple |
| Key → value lookups | dict |
| Unique items, fast membership tests, set algebra | set |
| Need both O(1) push AND O(1) pop from the front | collections.deque, not list |
7collections.deque — When Lists Aren't Enough
from collections import deque
q = deque([1, 2, 3])
q.appendleft(0) # O(1) — a plain list.insert(0, ...) would be O(n)
q.popleft() # O(1)
q.append(4) # O(1)deque is implemented as a doubly-linked list of fixed-size blocks, giving O(1) operations at both ends — the trade-off is O(n) random access by index, unlike a list's O(1) indexing.
Under the HoodHow CPython Actually Implements These▾
list: an over-allocated array of pointers
A list is a PyVarObject holding a pointer to a contiguous array of PyObject* — not the objects themselves, pointers to them (which is why a Python list can hold mixed types with no fixed element size). Critically, the array's allocated capacity is usually larger than its current length. When append() exceeds capacity, CPython grows the array by roughly 1.125x plus a small constant (listobject.c's growth pattern), not by exactly one slot — this is what makes repeated append() O(1) amortized rather than O(n) per call: most appends just write into already-allocated slack space, and the periodic full reallocation+copy is spread thin over many cheap appends.
import sys
lst = []
prev = sys.getsizeof(lst)
for i in range(10):
lst.append(i)
size = sys.getsizeof(lst)
if size != prev:
print(f"len={len(lst)}: buffer grew to {size} bytes")
prev = sizeRunning this shows the buffer growing in jumps, not once per append — direct evidence of over-allocation.
tuple: no over-allocation, because it can't grow
A tuple's array is allocated at exactly its final size when created — there's no growth strategy because tuples are immutable and their size never changes after construction. This makes tuples slightly more memory-efficient than lists of the same length and is one reason tuple creation for small, fixed collections is marginally cheaper.
dict: an open-addressing hash table, with a parallel insertion-order array
Since Python 3.6 (guaranteed in the language spec since 3.7), CPython's dict uses a "compact dict" layout: a sparse table of indices into a dense array of (hash, key, value) entries, where the dense array preserves insertion order. Looking up a key hashes it, probes the sparse index table (using open addressing — perturbing the probe sequence on collision, not chaining) to find which slot in the dense array holds that hash, then confirms equality. This split design is why dicts got both smaller (the sparse table only needs small integer indices, not full entries) and order-preserving in the same change — the insertion-order property fell out of the dense array's layout, not a separate linked list like some other languages' ordered maps use.
set: literally the same hash table machinery as dict, minus the values
CPython's set implementation shares its underlying hash-table code with dict (both descend from the same probing/resizing logic in the C source), storing only keys with no associated value slot. This is why sets and dicts have matching average-case complexity characteristics for membership/insertion/deletion.
Complexity summary (average case)
| Operation | list | tuple | dict | set | deque |
|---|---|---|---|---|---|
| Index access | O(1) | O(1) | — | — | O(n) |
| Append/add | O(1)* | — | O(1)* | O(1)* | O(1) both ends |
| Insert/pop front | O(n) | — | — | — | O(1) |
Membership (in) | O(n) | O(n) | O(1) | O(1) | O(n) |
| Key/value lookup | — | — | O(1) | — | — |
\* amortized, due to over-allocation growth strategy.
⚠️ Common Pitfalls
- Using
listfor frequent front-insertion/removal —.insert(0, x)and.pop(0)are both O(n); usecollections.dequeif you need queue-like behavior at both ends. - Assuming
dict/setiteration order is meaningful across different dicts — insertion order is guaranteed within one dict, but two dicts with the "same" keys inserted in different orders will iterate differently. - Using a mutable object (like a
list) as a dict key or set element — raisesTypeError: unhashable type, because hashability requires the value to never change after being hashed. Use atupleinstead if you need a compound, fixed key. - Checking membership with
inon alistin a hot loop — this is O(n) per check; converting to asetfirst turns repeated membership tests into O(1) average, often a large real-world speedup. - Slicing thinking it's free —
lst[1:]allocates and copies a whole new list; doing this repeatedly in a loop is O(n) per slice, not free.
📋 Quick Reference
lst.append(x); lst.pop() # O(1) amortized — use the END of a list
lst.insert(0, x); lst.pop(0) # O(n) — use collections.deque instead
d.get(key, default) # never raises KeyError
d.setdefault(key, default) # get-or-insert in one call
key in d / value in s # O(1) average — prefer over `in list`
from collections import deque # O(1) both-end queue
a | b, a & b, a - b, a ^ b # set algebra: union, intersect, diff, symmetric diff🎤 Interview Q&A
Q1Compare list, tuple, set and dict.core▾
list: ordered, mutable, O(1) append, O(n) membership. tuple: ordered, immutable, hashable if contents are. set: unique unordered items, O(1) membership. dict: key-value mapping, O(1) average lookup, insertion-ordered since 3.7.
- Why use a tuple? Fixed records, dict keys, and signalling immutability.
Q2Which collections module types are useful?core▾
defaultdict (default values for missing keys), Counter (counting, most_common), deque (O(1) appends/pops at both ends), namedtuple, OrderedDict (move_to_end), and ChainMap.
- Why deque for queues? list.pop(0) is O(n).
Q3What can be a dict key?core▾
Any hashable object: immutable built-ins (str, int, tuple of hashables, frozenset) and objects with consistent __hash__ and __eq__. Lists and dicts can't be keys.
- Custom class hashing rule? Equal objects must have equal hashes.
Q4How do you use heapq and bisect?senior▾
heapq implements a min-heap on a list (push/pop O(log n), top-k with nlargest); bisect finds insertion points in sorted lists (binary search) and inserts while keeping order.
- Max-heap? Push negated values.
Q5Shallow vs deep copy?core▾
list.copy(), dict.copy(), copy.copy() copy the container but share nested objects; copy.deepcopy() recursively copies everything.
- Classic bug?
[[0]*3]*3creates three references to the same inner list.
🛠️ Practice exercises
Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.