`list` internals

CPython’s list is a dynamic array of pointers to Python objects, with over-allocation to amortize append cost.

Layout

A list holds:

ob_size: current number of elements.
ob_allocated: capacity (slots reserved).
ob_item: pointer to a contiguous C array of PyObject* pointers.

Each slot holds a pointer to a Python object, not the object itself. So a list of 1M ints takes ~8 MB for pointers plus the ints’ own memory (which is shared among small ints).

Growth strategy

When ob_size == ob_allocated and you append, the list resizes. CPython’s growth pattern:

new_allocated = (newsize + (newsize >> 3) + 6) & ~3

Roughly 1.125x growth — more conservative than the common 2x in other languages. This amortizes append to O(1).

import sys

lst = []
for i in range(10):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))

# Growth steps (varies by implementation):
# 1 88
# 2 88
# 3 88
# 4 88
# 5 120
# 6 120
# 7 120
# 8 120
# 9 184
# 10 184

Operations and complexity

Operation	Time
`lst[i]` (read by index)	O(1)
`lst[i] = x` (write by index)	O(1)
`lst.append(x)`	O(1) amortized
`lst.pop()` (from end)	O(1)
`lst.pop(0)` (from front)	O(n) — must shift all
`lst.insert(0, x)`	O(n) — must shift
`lst.remove(x)`	O(n) — search + shift
`x in lst`	O(n) — linear scan
`len(lst)`	O(1)
`lst.sort()`	O(n log n) — Timsort
`lst[i:j]` (slice)	O(j - i) — copy

Front-of-list operations are slow because slots must shift. Use collections.deque for queue-like access — both ends are O(1).

from collections import deque
q = deque()
q.appendleft(x)   # O(1)
q.popleft()       # O(1)

Slicing creates copies

big = list(range(1_000_000))
sub = big[100:200]   # new list of 100 pointers — copies pointers, not objects

For read-only views, use numpy arrays or memoryview-style structures.

`del`, slicing, and shrinking

del lst[i] shifts in-place, O(n). The list keeps its over-allocated capacity unless many items are deleted; capacity might shrink only on resize boundaries.

lst.clear() is O(n) (decref each item) but releases capacity.

Sort: Timsort

Python’s sort() (and sorted()) use Timsort — a hybrid of merge sort and insertion sort:

Stable (preserves order of equal elements)
O(n log n) worst case, O(n) on already-sorted or partially-sorted data
Optimized for real-world data with runs

Custom sort key:

items.sort(key=lambda x: x.priority)             # one key
items.sort(key=lambda x: (-x.priority, x.name))  # multi-key, descending priority then name

reverse=True reverses the result; doesn’t affect stability.

List comprehensions vs `for` + `append`

# List comprehension — slightly faster, builds list with known capacity hints
result = [f(x) for x in items]

# Equivalent loop
result = []
for x in items:
    result.append(f(x))

The comprehension is ~30% faster on average due to bytecode optimization (LIST_APPEND is a single opcode; the loop version invokes the method).

Memory tip: prefer generators for one-pass

# Comprehension: builds full list — O(n) memory
total = sum([x ** 2 for x in big_iter])

# Generator expression: streamed — O(1) memory
total = sum(x ** 2 for x in big_iter)

Same syntax minus the brackets. Use generator expressions when feeding sum, max, any, all, join, etc.

Interview angle

“What’s the complexity of lst.append?” (O(1) amortized.) “Why amortized?” (Resizing is O(n) but happens rarely.)
“How would you implement a queue?” (collections.deque for O(1) both ends; list is O(n) at the front.)
“What sort algorithm does list.sort() use?” (Timsort — stable, adaptive.)
“Why is lst.insert(0, x) slow?” (O(n) shift; use deque.appendleft instead.)

list internals