skip to content

Why is Python's list.append amortized O(1) but list.insert(0, x) O(n)?

level: middleimportance: must knowfreq 65%

answer

  1. Spare capacity at one end only
  2. Growth is proportional, not fixed
  3. Total cost over a sequence, divided
  4. The front has to shift everything
  5. Geometric growth, roughly an eighth

basics

~20 s

append usually writes into a spare slot the list already reserved, and the occasional resize copies pointers into a proportionally larger array, so the cost averages to constant. insert(0, x) shifts every existing pointer right, on every call.

solid answer

~50 s

A CPython list is a contiguous array of object pointers plus a length and a capacity. `append` writes into the next free slot and bumps the length — constant time. When the length hits the capacity, CPython allocates a larger array and copies the pointers across, which costs O(n); but the new capacity is roughly the new size plus an eighth, so a resize at length n buys about n/8 free appends. Summed over n appends the total copy work is O(n), which is what **amortized** O(1) means: a bound on the whole sequence, not on one call. `insert(0, x)` gets no such help — the array is contiguous and there is no spare room at the front, so all n existing pointers shift one place right every time. `pop(0)` and `remove` are O(n) for the same reason, and building a list with repeated `insert(0, …)` is quadratic.

code

python · 7 lines
python
import timeit

back = "out = []\nfor i in range(20_000): out.append(i)"
front = "out = []\nfor i in range(20_000): out.insert(0, i)"

print("append:   ", round(timeit.timeit(back, number=1), 4), "s")
print("insert(0):", round(timeit.timeit(front, number=1), 4), "s")

go deeper

for a junior

Recall the practical rule and the reason behind it: adding to the end of a list is cheap, adding or removing at the front is not, because a list is one contiguous block and the front operation moves everything else along.

for a middle

Explain the mechanics precisely: spare capacity, a proportional growth on resize, the copy cost spread over the appends it enables, and the shift that makes insert(0), pop(0) and remove linear. Know that amortized is about totals, not averages over random input.

for a senior

Bring the operational angle: the resize is a real tail-latency spike with a transient memory peak, so pre-size when the length is known, and recognise a quadratic front-building loop in review before it reaches production data volumes.

for a principal

Own the container choice as a design decision — which access pattern the data structure is actually being asked for, and when a list is the wrong shape entirely — and set the expectation that internal growth constants are implementation details no code should depend on.

### The layout the whole answer rests on A CPython list is a header plus a pointer to a separately allocated, contiguous array of object pointers, plus a record of how many of those slots exist (the capacity) and how many are in use (the length). Eight bytes per slot on a 64-bit build. Elements are never stored inline; the array holds addresses. Two consequences follow immediately, and they are the whole question: * Writing at the **end** touches one slot, provided a spare one exists. * Writing at the **front** requires every existing pointer to move one place right, because the array is contiguous and index 0 must end up holding the new value. ### Why `append` is *amortized* O(1) `append` stores the pointer in the next free slot and increments the length. That is a couple of machine instructions — genuinely constant time. When the length reaches the capacity there is no free slot, so CPython allocates a bigger array and copies the existing pointers across. That single `append` costs O(n). The trick is how much bigger: the new capacity is roughly the new size plus an eighth of it plus a small constant, rounded — so on a current build you will see the capacity go 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108 and onward. It is **geometric growth with a ratio near 1.125**, not doubling, and "it doubles" is the single most common wrong detail offered in interviews. Geometric is what matters. A resize at length n hands you about n/8 free appends before the next one. Summing the copy work over n appends gives a geometric series that totals O(n), so the *average* cost per append is constant. That is precisely what **amortized** means: not "usually fast", not "average-case over random inputs", but a bound on the total cost of a sequence, divided across it, with no probabilistic assumption at all. Worst-case for a *single* append is still O(n). CPython also declines to over-allocate when a resize already jumps far ahead of the current length — building a list from an iterable that reports its length up front lands on an exactly sized array rather than one with slack. ### Why `insert(0, x)` is O(n), every time There is no spare capacity at the *front*. `insert(0, x)` shifts the whole block of existing pointers one slot right (a single bulk memory move, so the constant factor is small) and then writes the new pointer into slot 0. That is n pointer-moves on every call, and it never amortizes, because nothing is being banked for next time. Building a list of n items with repeated `insert(0, …)` is quadratic; the same list built with `append` is linear, and the gap is measurable in the hundreds of times at only tens of thousands of elements. `pop(0)` is the mirror image: remove slot 0 and shift everything left, O(n). `remove(x)` is O(n) for two reasons stacked — a linear scan to find the value, then a shift to close the hole. `pop()` with no argument, by contrast, just decrements the length, and is O(1). The bulk move is fast per byte, which is why the quadratic cost hides at small n and only becomes visible in the thousands. When the workload genuinely needs cheap insertion and removal at both ends, the standard library's double-ended queue (`collections.deque`) is the container designed for it — that is a topic of its own. ### The operational edges worth naming **Tail latency.** "Amortized O(1)" is a statement about totals. In a latency-sensitive loop a single append can still stall on a `realloc` plus a copy of n pointers, and during the copy both the old and new arrays may be live, briefly roughly doubling that array's memory. If the final size is known, pre-sizing with `[None] * n` and assigning by index, or building through the constructor or `extend` from a sized iterable, removes those resizes entirely. **Shrinking.** Popping from the end does eventually give the array back: when the length falls below roughly half the capacity, CPython reallocates smaller. `clear()` releases the array outright. What comes back goes to the interpreter's allocator, though, not necessarily to the operating system. **The number is not a contract.** The growth formula, the staircase and every size you print are CPython internals that have been tuned between releases. The *amortized O(1)* property is the part you can rely on and the part the interview is about. ### The answer in interview shape State the layout, say that spare capacity makes the common append constant, say that the capacity grows proportionally so the occasional copy averages out to constant, and say that the front has no spare capacity so every front insert or delete shifts n pointers. Then name the trap: a loop that builds a list by inserting at index 0 is quadratic.

  • Does a CPython list double its capacity on every resize?
    No — doubling is the usual wrong answer. The new capacity is about the new size plus an eighth of it plus a small constant, rounded, which produces a staircase like 4, 8, 16, 24, 32, 40, 52, 64, 76. Growth is still geometric, with a ratio near 1.125 rather than 2, so the amortized argument holds while wasting far less memory. The formula itself is an implementation detail.
  • If append is amortized O(1), when is a single append still slow?
    On the resize. That call reallocates and copies n pointers, and while the copy happens the old and new arrays can both be live, briefly roughly doubling that array's memory. It shows up as a latency spike, not as throughput loss. If the final length is known, pre-size with `[None] * n` and assign by index, or build through the list constructor or `extend` from an iterable that reports its length — both skip the intermediate resizes.
  • Does popping many elements off the end give the memory back?
    Yes, in stages: when the length falls below roughly half the capacity CPython reallocates a smaller array, and `clear()` or `del lst[:]` releases the array outright. What is freed returns to the interpreter's allocator, though, so the process's resident set size may not fall immediately — that is a property of the allocator, not of the list.

Adding a book to the end of a shelf that was built with spare space is instant; occasionally you buy a bigger shelf and move everything once. Adding a book at the very start means sliding every book along, every single time.

saying these in an interview costs you the question

  • Says append is O(1) in the worst case, never O(n)
  • Claims insert(0, x) is cheap because Python lists are linked lists
  • States that the list doubles its capacity on every resize
  • Explains amortized as average-case over random inputs
  • Thinks pop(0) and pop() cost the same
  • Believes a resize copies the elements rather than the pointers

context

resolving links…