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 doubles the space each time so those events are rare enough to average out to a constant. 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 — typically about double the size — copy every existing item 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. Suppose the list doubles its capacity at sizes 1, 2, 4, 8, 16 … To append n items, the total copying work is 1 + 2 + 4 + … + n, which comes to less than 2n — a constant amount of copying per append, spread out over all of them. 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

Never take a table on trust, this one included. Build the same list two ways:

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 "        # copies the whole string each round: O(n²)
    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")

Same shape as §10.4's front-versus-back result, and for the same reason: the ratio doubles when n doubles, so += is O(n²) and join is O(n). The fix is one habit — build a list, join once.

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.

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(),         200000),
    ("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 O(n log n) sort 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 tiers will not.

10.8Common mistakes

10.9Try it yourself

def unique_reversed(data):
    result = []
    for item in data:
        if item not in result:          # problem 1
            result = [item] + result    # problem 2
    return result

def unique_reversed(data):
    seen = set()
    result = []
    for item in data:
        if item not in seen:      # O(1)
            seen.add(item)
            result.append(item)   # O(1)
    result.reverse()              # O(n), once
    return result

10.10Self-check

10.11Homework

10.12Words from this week