CPython's list Implementation in C

TL;DR: list is a contiguous block of PyObject * plus two integers: ob_size (length) and allocated (capacity). Growth over-allocates by about an eighth, so appending is a pointer store in the common case.

Python’s list is a dynamic array: a contiguous block of pointers to PyObjects, with a separately tracked logical size and allocated capacity. In CPython that is implemented by PyListObject in Objects/listobject.c. This article traces the representation and the hot paths through the 3.15 source.

The object struct

Every Python object starts with PyObject_VAR_HEAD (ob_refcnt, ob_type, and ob_size). For lists the payload adds two fields:

c
// 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;

ob_size is the public length (len(list)); allocated is the capacity of the backing array. The two are kept distinct so that appending can usually reuse spare slots instead of reallocating. ob_item is NULL for an empty list, which lets an empty list carry no allocation at all.

Why two counters? Because “how many items are there” and “how much room do I have” are different questions, and conflating them means every append either reallocs or wastes memory.

Memory layout

text

+---------------------------+  <- PyObject_GC_New result
| ob_refcnt                 |
+---------------------------+
| *ob_type  (&PyList_Type)  |
+---------------------------+
| ob_size   (len)            |
+---------------------------+
| *ob_item  (PyObject **)    |
+---------------------------+
| allocated (capacity)       |
+---------------------------+
            |
            v
+---------------------------+  <- PyMem_Malloc / _PyListArray
| PyObject * (slot 0)       |
| PyObject * (slot 1)       |
| ...                       |
| PyObject * (slot allocated-1) |
+---------------------------+

In the free-threaded build (Py_GIL_DISABLED), the backing array is wrapped in a _PyListArray that stores its own allocated count, so the capacity can be read atomically from the pointer itself:

c
// Objects/listobject.c (Py_GIL_DISABLED)
typedef struct {
    Py_ssize_t allocated;
    PyObject *ob_item[];
} _PyListArray;

Allocation

PyList_New pops a PyListObject from a per-thread freelist (up to Py_lists_MAXFREELIST == 80) before falling back to PyObject_GC_New. For a positive size it allocates a zeroed array of exactly size slots:

c
// Objects/listobject.c
PyObject *PyList_New(Py_ssize_t size) {
    ...
    PyListObject *op = _Py_FREELIST_POP(PyListObject, lists);
    if (op == NULL) {
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        ...
    }
    if (size <= 0) {
        op->ob_item = NULL;
    }
    else {
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        ...
    }
    Py_SET_SIZE(op, size);
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

Note ob_size == allocated == size on construction: a list created with a known size has no spare capacity. Spare capacity only appears through growth.

list_new_prealloc is a variant used by slicing/concatenation/repeat: it allocates a list whose ob_size is 0 but whose allocated is size, so callers can fill the slots directly and set the size at the end. This avoids a second resize.

The append fast path

Appending is split into an inline fast path and a slow resize:

c
// Include/internal/pycore_list.h
static inline int
_PyList_AppendTakeRef(PyListObject *self, PyObject *newitem) {
    Py_ssize_t len = Py_SIZE(self);
    Py_ssize_t allocated = self->allocated;
    if (allocated > len) {
        PyList_SET_ITEM(self, len, newitem);   /* store pointer, no realloc */
        Py_SET_SIZE(self, len + 1);
        return 0;
    }
    return _PyList_AppendTakeRefListResize(self, newitem);
}

When there is spare capacity (allocated > len), append is just a store and an ob_size bump – no allocation, no memcpy. Only when the array is full does it call py_list_resize.

That last line is doing the real work: the only thing the hot path does is check whether there’s room. Everything else is the slow path’s problem.

Over-allocation strategy

py_list_resize is where the amortized linear-time behavior comes from. The new capacity is computed as

c
// Objects/listobject.c
new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;
/* Do not overallocate if the new size is closer to overallocated size
 * than to the old size. */
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;

So the growth pattern is roughly 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ... (an eighth of the size plus 6, rounded down to a multiple of 4). The second clause disables over-allocation when the request jumps by more than the planned slack (e.g. list.extend with a huge iterable), so a single large growth does not leave an enormous unused tail.

list_resize (the inlined wrapper) also short-circuits when existing capacity already covers the new size and the list is not shrinking below half its allocation (or is small, <= 32 slots, where realloc costs more than the memory saved):

c
// Objects/listobject.c
static inline int list_resize(PyListObject *self, Py_ssize_t newsize) {
    Py_ssize_t allocated = self->allocated;
    if (allocated >= newsize &&
        (newsize >= (allocated >> 1) || allocated <= LIST_SMALL_ALLOCATED)) {
        Py_SET_SIZE(self, newsize);
        return 0;
    }
    return py_list_resize(self, newsize);
}

Shrinking a list therefore normally keeps its buffer unless it has fallen to less than half capacity.

Gotcha: del my_list[:] (or list.clear()) empties the list but does not necessarily free the backing array immediately. CPython keeps the capacity around, which is a small but real memory surprise in long-running services.

Insert

ins1 resizes to n+1, shifts the tail right by one, and stores the new item. Because list_resize may replace ob_item, the pointer is re-read after resizing:

c
// Objects/listobject.c
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_RELEASE(items[i+1], items[i]);
    FT_ATOMIC_STORE_PTR_RELEASE(items[where], Py_NewRef(v));
    return 0;
}

Insertion is O(n) because of the memmove; append is the O(1)-amortized operation. The shift uses atomic stores on free-threaded builds.

Note items = self->ob_item after the resize. That’s not a style choice — list_resize can reallocate and move the array, so the old pointer would be dangling.

Deletion and clearing

list_clear empties the list before dropping references, to avoid re-entrancy when a __del__ runs:

c
// Objects/listobject.c
Py_ssize_t i = Py_SIZE(a);
Py_SET_SIZE(a, 0);
FT_ATOMIC_STORE_PTR_RELEASE(a->ob_item, NULL);
a->allocated = 0;
while (--i >= 0) {
    Py_XDECREF(items[i]);
}
free_list_items(items, use_qsbr);

list_pop handles the single-element case by calling list_clear, and otherwise memmoves the tail left and resizes down.

Sorting (timsort)

list.sort() is an adaptive, stable natural mergesort (timsort), described in Objects/listsort.txt. The implementation sets allocated = -1 for the duration of the sort so that any mutation (which would reset allocated to a non-negative value) is detected afterward:

c
// Objects/listobject.c
saved_ob_size = Py_SIZE(self);
saved_ob_item = self->ob_item;
saved_allocated = self->allocated;
Py_SET_SIZE(self, 0);
FT_ATOMIC_STORE_PTR_RELEASE(self->ob_item, NULL);
self->allocated = -1; /* any operation will reset it to >= 0 */

It also supports a key= function by precomputing keys into a parallel array, and detects homogeneous lists (all same type) to pick specialized compare functions (unsafe_long_compare, unsafe_latin_compare, etc.) with a fallback to safe_object_compare. Runs are found, extended to a computed minrun (at most 64), and merged with galloping. Temp storage of up to MERGESTATE_TEMP_SIZE (256) slots is kept on the stack.

This is the part people get wrong. The list is empty for the duration of the sort. If your key= function mutates the list you’re sorting, you get a RuntimeError — that’s the mutation detector doing its job.

Freelist

Exact PyListObjects (not subclasses) are recycled through a per-thread freelist of up to 80 entries:

c
// Objects/listobject.c
PyListObject *op = _Py_FREELIST_POP(PyListObject, lists);
...
if (PyList_CheckExact(op)) {
    _Py_FREELIST_FREE(lists, op, PyObject_GC_Del);
}

The list object itself is GC-tracked (_PyObject_GC_TRACK); the backing ob_item array is plain PyMem memory.

Key takeaways

list is a PyObject_VAR_HEAD plus ob_item (a PyObject **) and allocated (capacity); ob_size is the length.
Appending reuses spare slots with no allocation; growth over-allocates by ~1/8 (rounded to a multiple of 4) for amortized O(1) append.
Insertion and deletion are O(n) memmoves; capacity is retained unless the list shrinks below half.
list.sort() is timsort, temporarily empties the list (allocated = -1) to detect mutation, precomputes keys, and uses type-specialized compares.
Empty lists carry no backing array; list objects are recycled via an 80-deep freelist.