How Python's list actually works

Why append is fast and insert(0, x) is slow, what "amortized O(1)" really means, and when a list is the wrong tool.

Intermediate

4 min read

A list is an array, not a linked list

Python's list is a dynamic array: a contiguous block of memory holding pointers to objects, plus some slack capacity at the end. This one fact explains almost everything about a list's performance:

Index access, lst[i], is O(1). The interpreter computes the memory offset directly — it doesn't walk anything.
append(x) is O(1) amortized. If there's spare capacity at the end, it's a direct write. If not, Python allocates a new, larger block and copies everything over — but it over-allocates on growth, so this expensive copy happens rarely enough that the average cost per append stays constant.
insert(0, x) is O(n). Every existing element has to shift one slot to the right to make room at the front. Insert at an arbitrary index i is O(n − i) for the same reason.
pop() (from the end) is O(1). pop(0) (from the front) is O(n) — the mirror image of insert, for the mirror image of reasons.

"Amortized" — the part people memorize without understanding

Over-allocation is the mechanism. When a list outgrows its current block, CPython doesn't allocate space for exactly one more item — it grows by roughly 12.5%, so there's room for future appends to land without another reallocation:

import sys
 
lst = []
prev_size = sys.getsizeof(lst)
for i in range(10):
    lst.append(i)
    size = sys.getsizeof(lst)
    if size != prev_size:
        print(f"len={len(lst)}: block grew ({prev_size} -> {size} bytes)")
    prev_size = size

Running this shows the underlying buffer jumping in irregular steps, not growing by exactly one slot per append. Most calls to append are just writing into already-reserved space — O(1), no allocation at all. Occasionally, the buffer is full and Python has to allocate a bigger one and copy every existing pointer over — an O(n) operation. Averaged across a long sequence of appends, the expensive O(n) copies happen rarely enough, and get rarer as the list grows, that the average cost per append converges to a constant. That average-case constant time, despite occasional expensive operations, is exactly what "amortized O(1)" means — it is not a claim that every single append is cheap, only that the total cost over many appends divided by the number of appends is bounded by a constant.

Why this matters for real code

# Building a queue by inserting at the front — O(n) per insert, O(n^2) total
queue = []
for item in incoming:
    queue.insert(0, item)   # shifts every existing element
 
# The fix: append, then reverse once — or better, don't use a list at all
from collections import deque
queue = deque()
for item in incoming:
    queue.appendleft(item)  # O(1) — deque is a doubly linked list of blocks,
                             # not a single contiguous array

collections.deque exists specifically because list is the wrong structure for a queue. It supports O(1) append and pop from both ends, at the cost of O(n) random access by index — the opposite trade-off from list. Reaching for deque instead of list the moment you're inserting or removing from the front is one of the highest-value, lowest-effort optimizations available in everyday Python.

List vs. generator — the memory trade-off

# Holds every value in memory at once
squares = [x * x for x in range(10_000_000)]
 
# Produces one value at a time, on demand — near-zero memory overhead
squares = (x * x for x in range(10_000_000))

A list comprehension builds the entire result before you use any of it. A generator expression (parentheses instead of brackets) produces values lazily, one at a time, as something actually iterates over it. If you're going to consume the whole sequence exactly once — feeding it into a for loop, sum(), or any() — a generator does the same job with a fraction of the memory, because it never materializes the full sequence at once. The trade-off: a generator can only be iterated once and doesn't support indexing (gen[3] fails), since it isn't actually storing anything.

How Python's list actually works

A list is an array, not a linked list

"Amortized" — the part people memorize without understanding

Why this matters for real code

List vs. generator — the memory trade-off

Further reading