Python's containers and what they really cost

Why this lesson exists

The most common performance bug in interview code is not a bad algorithm — it is a good algorithm using the wrong container. Writing `if x in my_list` inside a loop turns an O(n) solution into O(n²) without changing a single line of the logic.

You cannot reason about complexity unless you know what each operation costs. This is that table, with the reasoning behind it.

Operation costs

list — a contiguous array

A Python list stores pointers in one contiguous block. That is why indexing is instant: the address is a simple offset calculation.

It is also why inserting at the front is O(n) — every later element has to shift up one slot. `pop(0)` has the same problem. If you find yourself doing either in a loop, you want a deque.

# BAD: pop(0) shifts every remaining element each time
queue = [start]
while queue:
    node = queue.pop(0)      # O(n) per call

# GOOD: deque pops from the front in constant time
from collections import deque
queue = deque([start])
while queue:
    node = queue.popleft()   # O(1)

Note: On a graph with 100,000 nodes this is the difference between milliseconds and minutes.

dict and set — hash tables

Both hash the key to pick a bucket, so lookup does not depend on how many items are stored. That is the O(1) average.

It is average, not worst case. Keys that collide heavily degrade toward O(n), which is why Python randomises string hashes per process — it makes deliberate collision attacks impractical.

Keys must be hashable, meaning immutable. A tuple works, a list does not. That is why `set(map(tuple, list_of_lists))` is such a common idiom.

Strings are immutable, and that has a cost

Every string operation creates a new string. Building one with `s += part` in a loop copies everything accumulated so far on each iteration, which is O(n²) overall.

Collect the pieces in a list and call `''.join(parts)` once. That computes the final length, allocates once, and copies each piece exactly once — O(total length).

x = [[0] * 3] * 2       # both rows are THE SAME list
x[0][0] = 9
print(x)                # [[9, 0, 0], [9, 0, 0]]

grid = [[0] * 3 for _ in range(2)]   # correct: independent rows

def f(x, acc=[]):       # default evaluated ONCE, at definition
    acc.append(x)
    return acc
print(f(1), f(2))       # [1, 2] [1, 2] — shared across calls

print(-10 // 3, -10 % 3)  # -4 2 — Python floors toward -infinity

Note: The aliased-row bug in particular ruins 2-D DP tables, and it is silent.