Dynamic Arrays: How a Python list Grows

"A raw array has a fixed size. A Python list pretends it doesn't — and the trick it uses to keep that promise is one of the most quietly clever things in your toolbox."

The Problem a list Solves

A low-level array is a fixed block — you declare its size and you're stuck with it. But you rarely know the final size in advance. A dynamic array hides that limitation: it grows as you append, so it feels unbounded. Python's list is a dynamic array (C++ calls it vector, Java calls it ArrayList — same idea everywhere).

The secret, which you already met in amortized analysis: a list keeps a backing array with spare room (its capacity) that's bigger than its actual length. Appends drop into the spare room for free (O(1)). When the spare runs out, the list allocates a bigger block — roughly doubling — copies everything over (O(n)), and goes back to having spare room. Because the doublings get exponentially rarer, append is amortized O(1).

Length Is Not Capacity

This is the distinction that explains everything: len(lst) is how many items you've stored; the capacity is how many it could hold before the next reallocation. You never see capacity directly in Python, but you can watch it via the reserved bytes. Knowing it exists is what makes "append is usually instant but occasionally pauses" stop being mysterious.

A dynamic array = a fixed array plus spare capacity plus a doubling rule. Length is what you stored; capacity is what fits before the next O(n) regrow. That gap is why append is amortized O(1).

The Operations and Their Real Costs

Because a list is contiguous, the cost of each operation falls right out of "where does stuff have to move?":

lst[i] read/write — O(1), address math.
lst.append(x) / lst.pop() — amortized O(1), work at the end, nothing shifts.
lst.insert(0, x) / lst.pop(0) — O(n), everything after the spot shifts.
x in lst — O(n), a linear scan (this is the hidden-loop trap from the Complexity track).
lst[a:b] slice — O(b−a), it copies that range into a new list.

Pippa's Confession

I used to build a queue with a plain list and call lst.pop(0) to dequeue. It worked perfectly on small tests and quietly turned my O(n) loop into O(n²) on real data, because every single pop(0) shifted the entire list left. Dad showed me collections.deque, which does front-pops in O(1). Same idea, right structure. The list isn't wrong — I was using its expensive end as if it were free.

Code

Length vs capacity, and operation costs·python

import sys

# Length vs capacity: watch reserved bytes jump while length climbs smoothly.
lst = []
for i in range(9):
    print(f"len={len(lst)}  reserved_bytes={sys.getsizeof(lst)}")
    lst.append(i)
# The byte count jumps at certain lengths (a reallocation) — that's capacity
# growing by doubling, while len just ticks up by 1 each time.

# The cost cheat-sheet, demonstrated:
lst = list(range(5))
lst.append(99)        # O(1) amortized — lands in spare capacity at the end
lst.pop()             # O(1) — removes from the end, nothing shifts
lst.insert(0, -1)     # O(n) — every element shifts right to open index 0
lst.pop(0)            # O(n) — every element shifts left to close the gap
print(3 in lst)       # O(n) — linear scan, no shortcut on a list
print(lst[1:4])       # O(k) — copies that slice into a new list

Exercise

You need to process items strictly in arrival order: add to the back, remove from the front, millions of times. Sketch why doing this with a list and pop(0) is O(n²) overall, then name the structure that makes it O(n). Bonus: which end of a Python list is the cheap end, and why?

Hint

Each pop(0) is O(n) and you do it n times → O(n²). collections.deque gives O(1) at both ends. The cheap end of a list is the back (append/pop) because nothing has to shift there.

The Problem a list Solves

Length Is Not Capacity

The Operations and Their Real Costs

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0