Run it
The over-allocation made visible with sys.getsizeof, then the three operations timed against each other so the O(1) and the O(n) are numbers rather than claims.
Why append is O(1) amortised
The list holds spare capacity beyond its length. append writes into that space and increments the length — a couple of operations.
When capacity runs out, CPython allocates a larger block, copies every pointer across, and frees the old one. The growth is roughly new = old + old/8 + constant, so about 12.5% over-allocation rather than doubling.
That resize is O(n). Spread across the many appends the new capacity accommodates, the average per append is constant — which is what amortised O(1) means.
| Operation | Complexity | Why |
|---|
lst[i] | O(1) | Offset into a contiguous block |
append | O(1) amortised | Writes into spare capacity |
pop() | O(1) | Removes from the end |
insert(0, x) | O(n) | Shifts every pointer right |
pop(0) | O(n) | Shifts every pointer left |
x in lst | O(n) | Linear scan |
len(lst) | O(1) | Stored, not counted |
lst[a:b] | O(b−a) | Allocates and copies |
The two O(n) rows at the front are the practical trap: pop(0) in a loop is O(n²) and reads as ordinary code. collections.deque gives O(1) at both ends.
Memory, and NumPy's advantage
A list of a million small integers holds a million 8-byte pointers, and each integer is a separate heap object with a header — 28 bytes each in CPython.
The total including the integer objects is far more — roughly 40MB.
A NumPy array of the same data stores raw 64-bit values contiguously: 8MB total, with no per-element objects. That is the memory argument, and there is a speed argument too: operations run in C over the whole array, and the data is cache-friendly because the values themselves are adjacent rather than scattered pointers.
| | Python list | NumPy array |
|---|
| Stores | Pointers to objects | Raw values |
| Mixed types | Yes | No — one dtype |
| 1M integers | ~40MB | 8MB |
| Element access | Fast | Fast |
| Whole-array arithmetic | Loop in Python | Vectorised in C |
| Append | O(1) amortised | Expensive — reallocates |
The last row matters: NumPy arrays are for fixed-size numeric data, and building one by appending defeats the purpose.
An array of pointers, not of objects
The block holds references, all the same size, which is why one list can hold an int, a string and another list at once. It is also why sys.getsizeof on a list of a million integers is far smaller than the integers themselves — the list only stores the pointers.
Because the references are contiguous and equally sized, element i lives at a computable address. That is the whole reason indexing is O(1) and a linked list is not.
Why append is amortised O(1)
CPython allocates more room than the list currently needs. Most appends write into a spare slot: one store, no allocation. When the block fills, a larger one is allocated and everything is copied — O(n), but only on that one append.
Because the growth is geometric, the copies are rare enough that the cost spread over n appends is constant each. That is what "amortised" means, and it is worth saying the word: any individual append can be the expensive one, which matters if you care about latency rather than throughput.
Why the front is expensive
insert(0, x) and pop(0) both have to move every other element one slot, so both are O(n). Doing either in a loop is O(n²), and that is the single most common accidental quadratic in Python — usually written as a queue.
collections.deque is the fix: a doubly linked list of blocks, O(1) at both ends. It gives up O(1) random access in exchange, which is almost always the right trade when you only touch the ends.
The aliasing consequences
Because a list holds references, copying has two levels — and this is where the bugs are.
Shallow copying is enough for immutable contents and not for nested mutable ones:
And the famous one:
[x] * n repeats the reference n times. Harmless for immutable values, a bug for mutable ones. Understanding that a list holds pointers is exactly what makes this predictable rather than mysterious.
Choosing another container
| Need | Use | Why |
|---|
| Add/remove at both ends | deque | O(1) at the front |
| Membership testing | set | O(1) instead of O(n) |
| Key-value lookup | dict | O(1) |
| Fixed record | tuple | Immutable, hashable, less memory |
| Numeric arrays | numpy.ndarray | Contiguous values, vectorised |
| Homogeneous numbers, no maths | array.array | Raw values, standard library |
| Sorted order maintained | bisect.insort or sortedcontainers | Ordered operations |
array.array is the under-known one: it stores raw values like NumPy but is in the standard library and supports append efficiently. Useful when you want the memory saving without a NumPy dependency.
Questions people ask
Is a Python list a linked list? No — a contiguous dynamic array of pointers, with O(1) indexing.
Why is insert(0, x) slow? Every existing pointer shifts one position. Use deque.appendleft.
By how much does it grow? Roughly 12.5% over-allocation, not doubling — a compromise between memory and copy frequency.
Why can a list hold mixed types? Because it stores pointers, and every pointer is the same size whatever it points at.
Does del lst[i] free memory? It removes the reference and shifts the remainder. The object is freed when nothing references it.
When should I use NumPy? Homogeneous numeric data, especially with arithmetic over the whole array — roughly five times less memory and far faster.
Recap in one screen
- A contiguous array of pointers with spare capacity, plus a stored length.
- Contiguity gives O(1) indexing and cache-friendly iteration; pointers allow mixed types at a memory cost.
- Append is O(1) amortised because of over-allocation; operations at the front are O(n) because everything shifts.
- Holding references is why
b = a shares, copy() is shallow, and [[0]*3]*3 repeats one row. - For homogeneous numeric data, NumPy or
array.array stores raw values and uses a fraction of the memory.