How Python Creates and Destroys Lists—and What the Free List Looks Like

After reviewing the underlying structure and growth strategy of Python lists, this article examines how a list is created, destroyed, and how the free‑list cache works.

List creation

The interpreter provides a single C API, PyList_New, which takes a size argument to specify the length of the underlying PyObject * array.

//Objects/listobject.c
PyObject *
PyList_New(Py_ssize_t size)
{
    // Declare a PyListObject* variable
    PyListObject *op;
    // The underlying array length must be >= 0
    if (size < 0) {
        PyErr_BadInternalCall();
        return NULL;
    }

    // PyList_MAXFREELIST is a macro that defines the free‑list capacity (default 80)
#if PyList_MAXFREELIST > 0
    // Get the free‑list from the interpreter state
    struct _Py_list_state *state = get_list_state();
    // If there are cached elements, reuse one
    if (PyList_MAXFREELIST && state->numfree) {
        state->numfree--;
        op = state->free_list[state->numfree];
        OBJECT_STAT_INC(from_freelist);
        _Py_NewReference((PyObject *)op);
    }
    else
#endif
    {
        // Allocate a new object via GC allocator
        op = PyObject_GC_New(PyListObject, &PyList_Type);
        if (op == NULL) {
            return NULL;
        }
    }
    // If size <= 0, the list holds no elements
    if (size <= 0) {
        op->ob_item = NULL;
    } else {
        // Allocate memory for the underlying array of pointers
        op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));
        if (op->ob_item == NULL) {
            Py_DECREF(op);
            return PyErr_NoMemory();
        }
    }
    Py_SET_SIZE(op, size);
    op->allocated = size;
    _PyObject_GC_TRACK(op);
    return (PyObject *) op;
}

The function first tries to obtain a PyListObject from the free‑list; if none is available, it allocates a new object with PyObject_GC_New. For a non‑zero size it allocates the underlying array with PyMem_Calloc, sets ob_size and allocated, and registers the object with the garbage collector.

The article notes that PyObject_New and PyObject_GC_New receive the same arguments, but the latter reserves an extra 16 bytes for the PyGC_Head used by the cyclic‑GC.

Memory‑size measurement

Two ways to measure a list’s memory are shown:

import sys

lst = []
print(lst.__sizeof__())   # 40
print(sys.getsizeof(lst)) # 56

sys.getsizeof

reports 16 bytes more because it includes the PyGC_Head, whereas __sizeof__ does not. For immutable objects such as strings or integers the two results match.

List destruction

When a PyListObject is deallocated, the interpreter first checks the free‑list. The free‑list can hold up to 80 cached list objects, stored in an array free_list[PyList_MAXFREELIST] with a counter numfree.

//Objects/listobject.c
static struct _Py_list_state *
get_list_state(void)
{
    PyInterpreterState *interp = _PyInterpreterState_GET();
    return &interp->list;
}

The deallocation routine list_dealloc performs the following steps:

static void
list_dealloc(PyListObject *op)
{
    Py_ssize_t i;
    PyObject_GC_UnTrack(op);
    Py_TRASHCAN_BEGIN(op, list_dealloc)
    if (op->ob_item != NULL) {
        i = Py_SIZE(op);
        while (--i >= 0) {
            Py_XDECREF(op->ob_item[i]);
        }
        PyMem_Free(op->ob_item);
    }
#if PyList_MAXFREELIST > 0
    struct _Py_list_state *state = get_list_state();
    if (state->numfree < PyList_MAXFREELIST && PyList_CheckExact(op)) {
        state->free_list[state->numfree++] = op;
        OBJECT_STAT_INC(to_freelist);
    }
    else
#endif
    {
        Py_TYPE(op)->tp_free((PyObject *)op);
    }
    Py_TRASHCAN_END
}

After releasing the underlying array and decrementing reference counts of its items, the list object itself is either placed back into the free‑list (if the cache is not full) or its memory is freed.

The article explains why the underlying array is not cached: keeping it would waste memory and could lead to dangling pointers if the array’s elements were still referenced. Releasing the array back to the system heap avoids these problems.

Free‑list reuse example

lst1 = [1, 2, 3]
print(id(lst1))  # 139671899367680
# Put into free‑list
del lst1

# Retrieve from free‑list
lst2 = [1, 2, 3]
print(id(lst2))  # 139671899367680

The printed IDs are identical, showing that the second list reuses the cached PyListObject from the free‑list while a fresh underlying array is allocated.

Trashcan mechanism

When deallocating deeply nested lists, Python employs a “trashcan” mechanism to limit recursion depth and avoid C‑stack overflow. The article demonstrates a recursive list of depth 2**20 that can be deleted safely because the trashcan defers deallocation.

L = None
for i in range(2**20):
    L = [L]

del L

The mechanism postpones the destruction of inner objects, preventing the interpreter from crashing.

Overall, the article clarifies the creation, destruction, and caching strategies of CPython lists, including the free‑list capacity, memory‑management decisions, and the trashcan safeguard for deep recursion.