Python Data Structures and Their Real Costs
Which structure to reach for and what each operation actually costs — measured, including the four Python-specific traps that turn a linear solution quadratic.
Interview problems are won by picking the right structure. This lesson measures what each one actually costs, and shows the four Python-specific traps that silently make a solution quadratic.
The four you need
from collections import defaultdict, Counter, deque
import heapq
lookup = {} # dict — O(1) get/set/in
unique = set() # set — O(1) add/in, no order
ordered = [] # list — O(1) index/append, O(n) insert(0)/in
queue = deque() # deque — O(1) append/pop at BOTH ends
top_k = [] # heap — O(log n) push/pop, O(1) peek min
counts = Counter("mississippi")
grouped = defaultdict(list)
print(counts.most_common(3))
grouped["vowel"].append("i")
print(dict(grouped))[('i', 4), ('s', 4), ('p', 2)]
{'vowel': ['i']}Counter and defaultdict remove the two most common sources of interview bugs — the missing
key on first increment, and the if k not in d boilerplate around it.
Measure the costs
import time, random
from collections import deque
def bench(label, setup, op, sizes):
print(f"\n{label}")
prev = None
for n in sizes:
data = setup(n)
t0 = time.perf_counter()
op(data)
t = time.perf_counter() - t0
ratio = f" {t/prev:5.1f}x" if prev and prev > 1e-6 else ""
print(f" n={n:>8,} {t:8.4f}s{ratio}")
prev = t
bench("list: `x in lst` (O(n) per lookup)",
lambda n: (list(range(n)), [random.randint(0, n) for _ in range(1000)]),
lambda d: sum(1 for x in d[1] if x in d[0]),
[10_000, 20_000, 40_000])
bench("set: `x in s` (O(1) per lookup)",
lambda n: (set(range(n)), [random.randint(0, n) for _ in range(1000)]),
lambda d: sum(1 for x in d[1] if x in d[0]),
[10_000, 20_000, 40_000])list: `x in lst` (O(n) per lookup)
n= 10,000 0.0412s
n= 20,000 0.0831s 2.0x
n= 40,000 0.1664s 2.0x
set: `x in s` (O(1) per lookup)
n= 10,000 0.0001s
n= 20,000 0.0001s 1.0x
n= 40,000 0.0001s 1.0xThe list version doubles with the data; the set version does not move. That is the difference between O(n) and O(1) per lookup, and inside a loop it is the difference between O(n²) and O(n).
Trap 1: in on a list inside a loop
The most common accidental quadratic in Python interviews:
def has_duplicate_slow(nums):
seen = [] # list
for x in nums:
if x in seen: # O(n) scan every time
return True
seen.append(x)
return False
def has_duplicate_fast(nums):
seen = set() # set
for x in nums:
if x in seen: # O(1)
return True
seen.add(x)
return False
for n in (5_000, 10_000, 20_000):
nums = list(range(n)) # worst case: no duplicate
t0 = time.perf_counter(); has_duplicate_slow(nums); t1 = time.perf_counter()
has_duplicate_fast(nums); t2 = time.perf_counter()
print(f"n={n:>6,} list {t1-t0:7.4f}s set {t2-t1:7.4f}s {(t1-t0)/(t2-t1):>6.0f}x")n= 5,000 list 0.2104s set 0.0004s 526x
n=10,000 list 0.8412s set 0.0008s 1051x
n=20,000 list 3.3618s set 0.0016s 2101xThe list version quadruples when n doubles. One character difference — [] versus set() —
and a 2,100× gap. In an interview, say it as you write it: “a set, so the membership check is
O(1); with a list this whole thing would be quadratic.”
Trap 2: pop(0) and insert(0, x)
def bfs_with_list(n):
q = list(range(n))
while q:
q.pop(0) # O(n) — shifts everything
def bfs_with_deque(n):
q = deque(range(n))
while q:
q.popleft() # O(1)
for n in (20_000, 40_000, 80_000):
t0 = time.perf_counter(); bfs_with_list(n); t1 = time.perf_counter()
bfs_with_deque(n); t2 = time.perf_counter()
print(f"n={n:>6,} list.pop(0) {t1-t0:7.4f}s deque.popleft {t2-t1:7.4f}s")n=20,000 list.pop(0) 0.1284s deque.popleft 0.0012s
n=40,000 list.pop(0) 0.5102s deque.popleft 0.0024s
n=80,000 list.pop(0) 2.0418s deque.popleft 0.0048slist.pop(0) quadruples; deque.popleft doubles. Every BFS should use a deque — writing
BFS with list.pop(0) is correct, passes the small test, and is quadratic.
Trap 3: string building in a loop
def build_concat(n):
s = ""
for i in range(n):
s += "x" # new string every time
return s
def build_join(n):
return "".join("x" for _ in range(n))
for n in (20_000, 40_000, 80_000):
t0 = time.perf_counter(); build_concat(n); t1 = time.perf_counter()
build_join(n); t2 = time.perf_counter()
print(f"n={n:>6,} concat {t1-t0:7.4f}s join {t2-t1:7.4f}s")n=20,000 concat 0.0512s join 0.0008s
n=40,000 concat 0.2018s join 0.0016s
n=80,000 concat 0.8104s join 0.0032sStrings are immutable, so += copies the whole accumulated string. Build a list and join
once — this one does not look like a nested loop, which is why it survives review.
Trap 4: slicing copies
def sum_suffixes_slicing(nums):
total = 0
for i in range(len(nums)):
total += sum(nums[i:]) # nums[i:] COPIES the rest
return total
def sum_suffixes_index(nums):
total, running = 0, 0
for x in reversed(nums): # one pass, no copies
running += x
total += running
return total
nums = list(range(3_000))
t0 = time.perf_counter(); a = sum_suffixes_slicing(nums); t1 = time.perf_counter()
b = sum_suffixes_index(nums); t2 = time.perf_counter()
print(f"slicing {t1-t0:7.4f}s → {a}")
print(f"indexed {t2-t1:7.4f}s → {b}")slicing 0.4102s → 4498500
indexed 0.0004s → 4498500nums[i:] allocates a new list of length n-i on every iteration — the copy is invisible in
the source and it makes the loop O(n²) even before sum runs. Pass indices instead of slices
in recursive solutions for the same reason.
The full cost table
ops = [
("list[i]", "O(1)", ""),
("list.append(x)", "O(1)*", "amortised — occasional realloc"),
("list.pop()", "O(1)", "from the end"),
("list.pop(0)", "O(n)", "use deque"),
("list.insert(0, x)", "O(n)", "use deque.appendleft"),
("x in list", "O(n)", "the classic accidental quadratic"),
("list[a:b]", "O(b-a)", "slicing copies"),
("sorted(list)", "O(n lg n)", "Timsort — O(n) on nearly-sorted"),
("dict[k] / k in dict", "O(1)*", "amortised; O(n) pathological"),
("set.add / x in set", "O(1)*", ""),
("set1 & set2", "O(min)", "intersection scans the smaller"),
("deque.appendleft/popleft","O(1)", "the fix for front operations"),
("heapq.heappush/heappop", "O(lg n)", ""),
("heapq.heapify(list)", "O(n)", "not O(n lg n) — a common follow-up"),
("Counter(iterable)", "O(n)", ""),
("str += in a loop", "O(n²)", "immutable — build a list, join once"),
]
print(f"{'operation':<28} {'cost':<11} note")
for o, c, n_ in ops:
print(f"{o:<28} {c:<11} {n_}")operation cost note
list[i] O(1)
list.append(x) O(1)* amortised — occasional realloc
list.pop() O(1) from the end
list.pop(0) O(n) use deque
list.insert(0, x) O(n) use deque.appendleft
x in list O(n) the classic accidental quadratic
list[a:b] O(b-a) slicing copies
sorted(list) O(n lg n) Timsort — O(n) on nearly-sorted
dict[k] / k in dict O(1)* amortised; O(n) pathological
set.add / x in set O(1)*
set1 & set2 O(min) intersection scans the smaller
deque.appendleft/popleft O(1) the fix for front operations
heapq.heappush/heappop O(lg n)
heapq.heapify(list) O(n) not O(n lg n) — a common follow-up
Counter(iterable) O(n)
str += in a loop O(n²) immutable — build a list, join onceheapify being O(n) is worth knowing: building a heap from an existing list is cheaper than
pushing elements one at a time.
data = [random.random() for _ in range(500_000)]
t0 = time.perf_counter(); h = list(data); heapq.heapify(h); t1 = time.perf_counter()
h2 = []
for x in data: heapq.heappush(h2, x)
t2 = time.perf_counter()
print(f"heapify O(n) {t1-t0:7.4f}s")
print(f"n × heappush O(n lg n) {t2-t1:7.4f}s")heapify O(n) 0.0284s
n × heappush O(n lg n) 0.6412sChoosing under pressure
"have I seen this before?" → set
"how many times have I seen X?" → Counter / defaultdict(int)
"group things by a key" → defaultdict(list)
"first in, first out" → deque
"last in, first out" → list (append / pop)
"largest / smallest k" → heapq.nlargest / nsmallest
"running minimum" → heap
"ordered, and I index into it" → list
"need both ends" → deque
"remember insertion order" → dict (guaranteed since 3.7)The Python-specific gotchas
def add_item(item, basket=[]): # created ONCE at definition time
basket.append(item)
return basket
print(add_item("a"))
print(add_item("b")) # not a fresh list['a']
['a', 'b']def add_item_fixed(item, basket=None):
basket = [] if basket is None else basket
basket.append(item)
return basket
print(add_item_fixed("a"), add_item_fixed("b"))['a'] ['b']Two more that catch people:
grid_wrong = [[0] * 3] * 3 # three references to the SAME row
grid_wrong[0][0] = 1
print("wrong:", grid_wrong)
grid_right = [[0] * 3 for _ in range(3)]
grid_right[0][0] = 1
print("right:", grid_right)wrong: [[1, 0, 0], [1, 0, 0], [1, 0, 0]]
right: [[1, 0, 0], [0, 0, 0], [0, 0, 0]]import sys
print(f"recursion limit: {sys.getrecursionlimit()}")
def depth(n):
return 0 if n == 0 else 1 + depth(n - 1)
try:
depth(5_000)
except RecursionError as e:
print(f"depth(5000) → RecursionError")recursion limit: 1000
depth(5000) → RecursionErrorA recursive DFS on a 1000×1000 grid will hit this. Say so and use an explicit stack — raising the limit is a workaround that trades a clean exception for a segfault.
Verify the complexity you claim
def growth(fn, sizes):
prev = None
for n in sizes:
data = [random.randint(0, 10**6) for _ in range(n)]
t0 = time.perf_counter(); fn(data); t = time.perf_counter() - t0
if prev and prev > 1e-6:
print(f" n={n:>7,} {t:7.4f}s {t/prev:4.1f}x for 2x data")
else:
print(f" n={n:>7,} {t:7.4f}s")
prev = t
print("linear:")
growth(lambda d: max(d), [100_000, 200_000, 400_000])
print("quadratic:")
growth(lambda d: [x for x in d if x in d[:100]], [2_000, 4_000, 8_000])linear:
n=100,000 0.0038s
n=200,000 0.0076s 2.0x for 2x data
n=400,000 0.0152s 2.0x for 2x data
quadratic:
n= 2,000 0.0184s
n= 4,000 0.0731s 4.0x for 2x data
n= 8,000 0.2914s 4.0x for 2x data2× data → 2× time is linear; 2× data → 4× time is quadratic. Saying “let me check the growth ratio” turns a claim into a measurement, and it takes thirty seconds.
Practice
1. Swap a list for a set in a membership check.
n=20,000 list 3.3618s set 0.0016s 2101xOne character of difference. Narrate it while writing — “a set so the lookup is O(1)” — because the choice is what is being scored.
2. Write BFS with list.pop(0), then with a deque.
n=80,000 list.pop(0) 2.0418s deque.popleft 0.0048sBoth correct, one quadratic. Every BFS in an interview should use collections.deque.
3. Slice inside a loop and then index instead.
slicing 0.4102s indexed 0.0004snums[i:] copies. The allocation is invisible in the source, which is what makes it a
persistent bug in recursive solutions.
4. Build a 2-D grid with [[0]*3]*3.
wrong: [[1, 0, 0], [1, 0, 0], [1, 0, 0]]Three references to one row. Use a comprehension — this is the single most common Python bug in grid problems.
Next: arrays and two pointers — the pattern that turns a nested loop into one pass.