What Python Lists Really Cost

10.1What a list really is

Picture a row of numbered lockers, side by side, with no gaps. That is a Python list: a block of slots in order, each holding a reference to a value.

Two consequences follow from the "no gaps" part, and they explain everything else:

• Reading a position is instant. To find item 4 719, the computer computes where the slot is and goes there. Length is irrelevant: O(1).
• Inserting or removing at the front is expensive. If you take out the first locker, everything behind it has to shuffle forward one place to close the gap. That is n moves: O(n).

10.2The cost table

* append is O(1) amortised: occasionally Python has to move the whole list into a bigger block of memory, which costs O(n), but it reserves extra capacity so total resizing work across many appends remains linear. The exact growth policy depends on the implementation. The next section watches that happen.

10.3Amortised append: watching the list grow

The lockers picture has one loose end: what happens when the row is full and you append one more? There is no free slot behind the last one. Python's answer is to rent a bigger row with spare capacity, potentially copy the existing references across, and then write the new one. That copy is O(n). So how can we call append cheap?

Because the expensive copies are rare, and they get rarer as the list grows. Use an idealised doubling model with capacities 1, 2, 4, 8, 16 …; this is not Python's literal allocation policy. For n items where n is a power of two, copying costs 1 + 2 + … + n/2 = n − 1. Together with n new writes, that is 2n − 1 units: a constant amortised cost per append. Other n also give linear total work. Sharing the cost of the rare big events across the many cheap ones is called amortising, and it is why we quote append as O(1).

You can see the capacity jumps directly. sys.getsizeof reports how many bytes a list occupies; watch it step up in chunks, not smoothly, as we append:

import sys

data = []
last = -1
for i in range(17):
    size = sys.getsizeof(data)
    if size != last:                       # only print when it jumps
        print(f"len={len(data):>2}   {size} bytes  <- grew here")
        last = size
    else:
        print(f"len={len(data):>2}   {size} bytes")
    data.append(i)

Most appends land in already-rented space and cost nothing extra — those are the flat stretches. Only at a jump does Python copy the list into a bigger block, and each block lasts longer than the last, so the jumps thin out. Averaged over the whole run, the cost per append settles to a constant. That is exactly what "O(1) amortised" means: usually cheap, occasionally dear, constant on average.

10.4Measuring it: front versus back

Test the model yourself. These builders use the same values but produce opposite orders: append preserves their arrival order, while front insertion reverses it. If order matters, include a final O(n) reversal when comparing equivalent outputs.

import time

def build_append(n):
    data = []
    for i in range(n):
        data.append(i)          # cheap end
    return data

def build_insert_front(n):
    data = []
    for i in range(n):
        data.insert(0, i)       # expensive end
    return data

for n in [10000, 20000, 40000, 80000]:
    start = time.perf_counter(); build_append(n)
    t_app = time.perf_counter() - start

    start = time.perf_counter(); build_insert_front(n)
    t_ins = time.perf_counter() - start

    print(f"n={n:>6}  append {t_app:.4f}s   insert(0) {t_ins:.4f}s   ratio {t_ins/t_app:,.0f}x")

Read the ratio column: it doubles every time n doubles. That is the fingerprint of one method being O(n) overall while the other is O(n²) — because n insertions at O(n) each is n × n. The two loops look almost identical on the page. One of them is a bomb with a slow fuse.

10.5Building strings and lists the fast way

The same trap appears when you build a list or a string by repeated concatenation. result = result + [x] creates a whole new list each round.

import time

def by_concat(n):
    result = []
    for i in range(n):
        result = result + [i]        # new list every time: O(n) each
    return result

def by_append(n):
    result = []
    for i in range(n):
        result.append(i)             # O(1) each
    return result

def by_comprehension(n):
    return [i for i in range(n)]     # same work, less Python overhead

def by_list_range(n):
    return list(range(n))            # all the work happens in C

for func in [by_concat, by_append, by_comprehension, by_list_range]:
    start = time.perf_counter()
    func(20000)
    print(f"{func.__name__:>18}: {time.perf_counter() - start:.5f}s")

A factor of over a thousand between the first and the last, for code that produces an identical result. The first is O(n²); the other three are O(n) with progressively smaller constants. Note the two different kinds of improvement on display: the jump from by_concat to by_append is a class change and it grows with n; the jump from by_append to list(range(n)) is a constant factor and it does not.

import time

def by_plus(n):
    text = ""
    for i in range(n):
        text += "word "        # repeated concatenation; runtime optimisations may affect scaling
    return text

def by_join(n):
    pieces = []
    for i in range(n):
        pieces.append("word ")  # O(1) each
    return "".join(pieces)      # one linear pass at the end

for n in [25000, 50000, 100000]:
    start = time.perf_counter(); by_plus(n)
    p = time.perf_counter() - start
    start = time.perf_counter(); by_join(n)
    j = time.perf_counter() - start
    print(f"n={n:>6}   += {p:.4f}s   join {j:.4f}s   ratio {p/j:,.0f}x")

These illustrative timings show the repeated-copy model; they are not a guaranteed output of this interpreter-dependent experiment. Record your actual ratios, even if += scales nearly linearly. Building pieces and joining once gives a predictable linear construction in the total number of characters.

10.6When you need a fast front: deque

Sometimes you genuinely need to add and remove at both ends — a queue of jobs, a history of moves. Python has a structure built for it.

from collections import deque
import time

n = 100000

data = list(range(n))
start = time.perf_counter()
while data:
    data.pop(0)                      # O(n) each → O(n²) total
print(f"list.pop(0):    {time.perf_counter() - start:.3f}s")

data = deque(range(n))
start = time.perf_counter()
while data:
    data.popleft()                   # O(1) each → O(n) total
print(f"deque.popleft(): {time.perf_counter() - start:.3f}s")

Three hundred times faster, and the gap widens with n. You do not need to know how a deque works internally to use it. You do need the habit of asking "is there a structure designed for the operation I keep repeating?" — which is the whole of next week.

10.7Measuring every operation at once

You have measured a few operations one pair at a time. Here is a single harness that times all the headline operations at a fixed size, so the O(1) rows and the O(n) rows sit next to each other and the difference is impossible to miss. The O(1) operations are far too fast to time once, so we repeat each many times inside the timed region and report the time per operation. Each repeat gets fresh input. Append grows its list, while pop removes 50 000 of the available 100 000 items; these are averages over changing sizes, not fixed-size single-operation measurements. The front-removal row drains its 2 000-item list exactly once. The output below is illustrative, and sorting this already sorted input exercises the adaptive best case.

import time

n = 100000
base = list(range(n))

def time_op(setup, op, repeats):
    """Best-of-3 total time for running op() `repeats` times."""
    best = None
    for _ in range(3):
        data = setup()
        start = time.perf_counter()
        for _ in range(repeats):
            op(data)
        t = time.perf_counter() - start
        if best is None or t < best:
            best = t
    return best / repeats            # seconds per single operation

fresh = lambda: list(range(n))

rows = [
    ("index read   data[n//2]", fresh, lambda d: d[n // 2],        200000),
    ("append       d.append(0)", fresh, lambda d: d.append(0),     200000),
    ("pop end      d.pop()",     fresh, lambda d: d.pop(),          50000),
    ("insert(0)    d.insert(0,0)", lambda: list(range(2000)), lambda d: d.insert(0, 0), 2000),
    ("pop(0)       d.pop(0)",    lambda: list(range(2000)), lambda d: d.pop(0),      2000),
    ("membership   -1 in d",     fresh, lambda d: (-1 in d),          200),
    ("sort         sorted(d)",   fresh, lambda d: sorted(d),           50),
]

print(f"{'operation':>26}   {'sec / op':>12}")
for label, setup, op, reps in rows:
    per = time_op(setup, op, reps)
    print(f"{label:>26}   {per*1e9:>9,.0f} ns")

Read it as three tiers. The O(1) operations — index, append, pop from the end — all sit around a few dozen nanoseconds, flat and cheap. The front operations insert(0) and pop(0) are twenty to fifty times dearer even on a much shorter list, because each one shifts the whole tail. The O(n) scans (in a missing value) and the sort of this already ordered list are in a different world entirely — a missing-value membership test on 100 000 items is nearly forty thousand times slower than an index read. The numbers on your machine will differ; the work models explain the expected trends, but precise relative tiers can vary.

10.8Common mistakes

10.11Optional Studio Extension

10.12Words from this week