vault

CPython List Internals

12 min read

CPython List Internals

A CPython list is not a linked list and not an array of values — it is a dynamic array of PyObject* pointers. The list object itself is a small fixed-size header (PyListObject) holding a pointer ob_item to a separately heap-allocated C array of object pointers, the count of slots currently in use (ob_size, inherited from the variable-object header), and the count of slots actually allocated (allocated). The capacity-vs-length split, together with a mild over-allocation strategy in list_resize, is what makes append amortized O(1). Because the array holds pointers, a list is a vector of references — the elements live elsewhere on the heap, and the list neither owns their layout nor stores them contiguously. (Verified against CPython 3.14: Objects/listobject.c and Include/cpython/listobject.h.)

Mental Model

Think of a list as a thin handle wrapping a resizable C pointer-array. The handle (the PyListObject struct) is a fixed, small object that the rest of the interpreter passes around. It contains three numbers that matter: where the backing array is (ob_item), how many of its slots are live (ob_size), and how big the backing array actually is (allocated). The gap between ob_size and allocated is spare capacity — slots that have been paid for but are not yet used. Appends consume spare capacity for free; only when the spare runs out does the list pay to grow the backing array.

graph LR
    subgraph Handle["PyListObject (fixed-size header)"]
        H1["ob_refcnt"]
        H2["ob_type → PyList_Type"]
        H3["ob_size = 3  (length)"]
        H4["ob_item ──┐"]
        H5["allocated = 4  (capacity)"]
    end
    subgraph Array["ob_item: heap C array of PyObject*"]
        A0["[0] ●──→ int 10"]
        A1["[1] ●──→ str 'hi'"]
        A2["[2] ●──→ list [...]"]
        A3["[3] (unused spare)"]
    end
    H4 --> A0

Diagram: a 3-element list with capacity 4. The header is one allocation; the pointer array ob_item is a second, separate allocation. Each live slot is a PyObject* pointing at an object that lives independently on the heap. The insight: there are two allocations (header + backing array), the array stores references not values, and slot [3] is over-allocated spare capacity that lets the next append skip a realloc.

The PyListObject Struct

The struct is defined in Include/cpython/listobject.h:

typedef struct {
    PyObject_VAR_HEAD
    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */
    PyObject **ob_item;
 
    /* ob_item contains space for 'allocated' elements.  The number
     * currently in use is ob_size.
     * Invariants:
     *     0 <= ob_size <= allocated
     *     len(list) == ob_size
     *     ob_item == NULL implies ob_size == allocated == 0
     * list.sort() temporarily sets allocated to -1 to detect mutations.
     * ...
     */
    Py_ssize_t allocated;
} PyListObject;

Walking it field by field:

  • PyObject_VAR_HEAD expands to the standard variable-length object header: a reference count (ob_refcnt), a type pointer (ob_type, here &PyList_Type), and ob_size — the length of the list, len(list) == ob_size. “VAR” (variable) means CPython treats the logical size as part of the header even though, unlike a tuple, the storage is not inline.
  • ob_item is a PyObject ** — a pointer to a C array of PyObject*. list[i] is exactly ob_item[i]. This array is a separate heap allocation from the header.
  • allocated is the capacity: the number of slots the ob_item array can hold before it must be reallocated. The invariant 0 <= ob_size <= allocated is the whole game — ob_size is how many you are using, allocated is how many you have room for.

The comment about list.sort() setting allocated = -1 is a mutation tripwire: while sorting, the comparison callbacks could re-enter Python and mutate the list out from under the sort; the sentinel -1 lets sort detect that the array was swapped and raise rather than corrupt memory.

Why a List Stores Pointers, Not Values

Python is dynamically typed: any slot can hold an int, a str, another list, a user-defined object — values of wildly different sizes and layouts. A C array of fixed-stride elements cannot hold heterogeneous values directly. CPython resolves this the way every object is represented: everything is a heap-allocated PyObject, and you refer to it by pointer. So a list slot is a uniform 8-byte (on 64-bit) PyObject*. The list is therefore a vector of references, and the objects it “contains” are shared, not copied — b = [a] makes the slot point at the same object a, which is why mutating a is visible through b[0].

This is also why sys.getsizeof(a_list) does not count the size of the elements: it reports the header plus the allocated-sized pointer array, not the objects the pointers reach. The integers, strings, and sub-lists each carry their own size, accounted separately.

The Growth Formula: How append Is Amortized O(1)

All resizing funnels through list_resize in Objects/listobject.c. The relevant logic:

static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
    size_t new_allocated, target_bytes;
    Py_ssize_t allocated = self->allocated;
 
    /* Bypass realloc() when a previous overallocation is large enough
       to accommodate the newsize.  If the newsize falls lower than half
       the allocated size, then proceed with the realloc() to shrink the list. */
    if (allocated >= newsize && newsize >= (allocated >> 1)) {
        assert(self->ob_item != NULL || newsize == 0);
        Py_SET_SIZE(self, newsize);
        return 0;
    }
    /* ... over-allocation ... */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
    if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
        new_allocated = ((size_t)newsize + 3) & ~(size_t)3;
    if (newsize == 0)
        new_allocated = 0;
    /* ... realloc to new_allocated * sizeof(PyObject*) ... */
}

Reading the fast path first: if the requested newsize already fits in allocated and is at least half of allocated, the function just updates ob_size (Py_SET_SIZE) and returns without touching the heap. That single branch is why most appends cost nothing but an integer store — the spare capacity absorbs them. The lower bound newsize >= (allocated >> 1) (half of allocated) means a list only shrinks its backing array once it has dropped below half-full, giving hysteresis so that a sequence of append/pop near a power-of-two boundary does not thrash realloc.

The growth formula, symbol by symbol:

new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
  • newsize — the new logical length being requested (for an append, the old length plus one).
  • (newsize >> 3) — newsize divided by 8 (a right shift of 3 bits), i.e. a 12.5% headroom proportional to current size. Over-allocating proportionally is what guarantees amortized O(1): each grow roughly multiplies capacity by a constant factor (~1.125 plus the constant 6), so the number of reallocs over n appends is O(log n) and the total bytes copied is a geometric series summing to O(n) — O(1) per append on average.
  • + 6 — a small additive constant so tiny lists still get a few free slots, avoiding a realloc on the very first appends.
  • & ~(size_t)3 — bitwise-AND with the complement of 3 clears the low two bits, rounding down to a multiple of 4. This keeps the allocation a clean multiple of 4 pointers (32 bytes on 64-bit).

The source comment spells out the resulting capacity sequence: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, .... So an empty list that you append into goes 0 → 4 slots on the first append, then stays at 4 for appends 2–4, jumps to 8, and so on. Note this is not doubling — it is mild over-allocation (~1/8), which trades a little extra reallocation work for substantially lower memory waste than a naive 2x policy.

The second branch handles bulk operations like extend:

if (newsize - Py_SIZE(self) > (Py_ssize_t)(new_allocated - newsize))
    new_allocated = ((size_t)newsize + 3) & ~(size_t)3;

If the jump in size (newsize - Py_SIZE(self)) is larger than the over-allocation the formula would grant, the proportional headroom is pointless — so it falls back to allocating just newsize rounded up to a multiple of 4, with no growth padding. This stops a single huge extend from over-allocating a second huge chunk on top.

Free-threaded build allocates a separate array struct

Under the experimental free-threaded build (Py_GIL_DISABLED, PEP 703), list_resize does not call PyMem_Realloc in place. It allocates a fresh _PyListArray, memcpys the old contents in, and publishes the new pointer with an atomic release store so concurrent readers see a consistent array. The default (GIL-enabled) build uses the simpler PyMem_Realloc path shown above. Both follow the identical growth formula. (Verified in 3.14 list_resize, #ifdef Py_GIL_DISABLED branch.)

Insert and pop(0): The O(n) Shift

Appending and popping at the end are cheap because they touch only the tail slot. Operations at the front or middle are O(n) because every following pointer must be moved over by one slot. The two paths use different machinery, and it is worth being precise about which.

list.insert(i, v) goes through ins1:

static int
ins1(PyListObject *self, Py_ssize_t where, PyObject *v)
{
    Py_ssize_t i, n = Py_SIZE(self);
    PyObject **items;
    /* ... */
    if (list_resize(self, n+1) < 0)
        return -1;
    if (where < 0) { where += n; if (where < 0) where = 0; }
    if (where > n) where = n;
    items = self->ob_item;
    for (i = n; --i >= where; )
        FT_ATOMIC_STORE_PTR_RELAXED(items[i+1], items[i]);
    FT_ATOMIC_STORE_PTR_RELEASE(items[where], Py_NewRef(v));
    return 0;
}
  • list_resize(self, n+1) grows the list by one element (possibly triggering the realloc above).
  • The where clamping normalizes negative and out-of-range indices Python-style.
  • The for loop is the cost: it walks from the last element down to where, copying each pointer one slot to the right — items[i+1] = items[i]. This is an explicit element-by-element shift, not a memmove; the stores are FT_ATOMIC_STORE_PTR_RELAXED so that a free-threaded reader never observes a torn pointer. It runs n - where iterations, so insert(0, v) shifts the whole list: O(n).
  • Finally Py_NewRef(v) increments the new element’s refcount (the list now holds a reference) and stores it into the freed where slot.

list.pop(i) goes through list_pop_impl, which uses memmove:

PyObject **items = self->ob_item;
v = items[index];
const Py_ssize_t size_after_pop = Py_SIZE(self) - 1;
if (size_after_pop == 0) {
    Py_INCREF(v);
    list_clear(self);
}
else {
    if ((size_after_pop - index) > 0) {
        memmove(&items[index], &items[index+1],
                (size_after_pop - index) * sizeof(PyObject *));
    }
    status = list_resize(self, size_after_pop);
}
  • v = items[index] grabs the popped pointer (its reference is handed back to the caller, so no decref here).
  • If index is not the last element, memmove slides the (size_after_pop - index) pointers after it down by one slot to close the hole. pop(0) moves nearly the entire array: O(n). pop() (default last element) moves nothing: O(1).
  • list_resize(self, size_after_pop) shrinks the logical size and, if it has fallen below half capacity, reallocates smaller.

The practical takeaway: a list is a stack at its tail (O(1) append/pop()) and a queue at its head only at O(n) cost. For FIFO workloads use collections.deque, which is a doubly linked list of fixed-size blocks with O(1) at both ends.

The List Free List

Creating and destroying small objects rapidly would hammer the allocator, so CPython keeps a free list of recently deallocated PyListObject headers and reuses them. The size constant lives in Include/internal/pycore_freelist_state.h:

#  define Py_lists_MAXFREELIST 80

So up to 80 dead list headers are retained per interpreter. On allocation, _Py_FREELIST_POP(PyListObject, lists) returns a recycled header instead of mallocing one; on deallocation, _Py_FREELIST_FREE(lists, op, PyObject_GC_Del) parks the header back on the free list (until the cap of 80 is hit, after which it is genuinely freed).

A crucial distinction: the free list recycles only the small fixed-size header object, not the variable-length ob_item backing array. The backing array is always allocated and freed separately via PyMem_Realloc / its free path — it cannot be pooled by a single-size free list because its size varies per list. So reusing a header saves one PyObject_GC_New-sized allocation; the capacity buffer is still bought and sold per list.

In 3.14 these free lists are part of the per-interpreter / per-thread _Py_freelists state struct (struct _Py_freelist lists;), reachable through _Py_freelists_GET() — a change from the older single global free-list arrays, so that sub-interpreters and free-threaded threads do not contend on a shared list. The 80 cap is unconditional: in pycore_freelist_state.h at v3.14.5 every *_MAXFREELIST constant is a bare #define with no #if Py_GIL_DISABLED / #ifdef Py_DEBUG guard, so no build mode redefines or disables it. The two build modes differ only in where the freelist lives, not in the cap value: _Py_freelists_GET() in pycore_freelist.h returns the per-thread _PyThreadStateImpl::freelists under Py_GIL_DISABLED and the per-interpreter interp->object_state.freelists otherwise, while Py_DEBUG only adds a thread-state null assertion. So Py_lists_MAXFREELIST == 80 is the live cap in every 3.14.5 build configuration.

Common Misunderstandings

“A Python list is a linked list.” No — it is a contiguous dynamic array of pointers. Random access list[i] is O(1); there are no per-element link nodes.

“Lists store their elements contiguously.” Only the pointers are contiguous. The objects pointed at are scattered across the heap, so iterating a list is not cache-friendly the way iterating a NumPy array of machine ints is — every element access chases a pointer.

“append is sometimes O(n), so it is not O(1).” Individual appends that trigger a realloc are O(n) in that moment, but because over-allocation makes those reallocs geometrically rare, the amortized cost per append is O(1). The distinction is between worst-case-single-operation and amortized-over-a-sequence.

“del list[0] or list.pop(0) is cheap.” It is O(n) — every subsequent pointer is shifted down. Repeatedly popping the front of a large list is a classic accidental O(n²).

See Also

Graph View

Backlinks