Inside Python’s ListObject: How PyList_New, list_resize, and the Free List Work

Definition

typedef struct { PyObject_VAR_HEAD PyObject **ob_item; Py_ssize_t allocated; } PyListObject;

The PyListObject is a variable‑size object. Its fields are: PyObject_VAR_HEAD: header for variable‑size objects. PyObject **ob_item: pointer array to the list elements (e.g., ob_item[0]). Py_ssize_t allocated: total allocated slots. ob_size (from the header): number of used slots.

Construction

Only one public function creates a new list:

PyObject *PyList_New(Py_ssize_t size) { PyListObject *op; size_t nbytes; #ifdef SHOW_ALLOC_COUNT static int initialized = 0; if (!initialized) { Py_AtExit(show_alloc); initialized = 1; } #endif if (size < 0) { PyErr_BadInternalCall(); return NULL; } if ((size_t)size > PY_SIZE_MAX / sizeof(PyObject *)) { PyErr_NoMemory(); } nbytes = size * sizeof(PyObject *); if (numfree) { numfree--; op = free_list[numfree]; } else { op = PyObject_GC_New(PyListObject, &PyList_Type); if (op == NULL) { PyErr_NoMemory(); return NULL; } } memset(op->ob_item, 0, nbytes); Py_SIZE(op) = size; op->allocated = size; _PyObject_GC_TRACK(op); return (PyObject *)op; }

The function first checks the free‑list; if a cached object is available it reuses it, otherwise it allocates a new object with PyObject_GC_New. It then allocates memory for the item array, initializes it to zero, sets ob_size and allocated, tracks the object with the GC, and returns it.

Simplified Steps

Check whether the list free‑list is empty; if not, reuse an object.

If the free‑list is empty, allocate memory from the heap.

Initialize the newly allocated memory.

list_resize

The list_resize function adjusts the allocated size of a list:

int list_resize(PyListObject *self, Py_ssize_t newsize) { // ... core logic ... if (allocated >= newsize && newsize >= (allocated >> 1)) { // shrink in place Py_SIZE(self) = newsize; return 0; } // otherwise allocate a new buffer size_t new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6); new_allocated += newsize; // ... reallocation and copy ... Py_SIZE(self) = newsize; self->allocated = new_allocated; return 0; }

If the current allocation can accommodate the new size (within half the current allocation), the function simply updates ob_size. Otherwise it computes a new allocation size, allocates a new buffer, copies existing items, and updates allocated and ob_size.

Free List and Recycling

Python keeps a free‑list of up to PyList_MAXFREELIST (default 80) PyListObject structures to avoid frequent malloc/free calls:

static PyListObject *free_list[PyList_MAXFREELIST]; static int numfree = 0;

When a list is deallocated, list_dealloc frees the items, releases the item array, and if the free‑list is not full, stores the list object for later reuse:

static void list_dealloc(PyListObject *op) { PyObject_GC_UnTrack(op); Py_TRASHCAN_SAFE_BEGIN(op); if (op->ob_item != NULL) { for (Py_ssize_t i = Py_SIZE(op) - 1; i >= 0; i--) { Py_XDECREF(op->ob_item[i]); } PyMem_FREE(op->ob_item); } if (numfree < PyList_MAXFREELIST) { free_list[numfree++] = op; } else { PyObject_GC_Del(op); } Py_TRASHCAN_SAFE_END(op); }

List Operations

Insert

Resize to size+1.

Determine insertion point.

Shift elements after the point.

Store the new element.

Append

Resize to size+1.

Place the new element at ob_item[ob_size].

Extend

Compute new total size m+n.

Resize to that size.

Copy the n new items starting at ob_item + m.

Delete

Find the index of the element to remove.

Decrement reference count of that element.

Shift subsequent elements left.

Examples

Creating a list and inserting at the front:

>> a = [1, 2, 3] >>> a.insert(0, 9) >>> a [9, 1, 2, 3]

Appending an element:

>> a = [1, 2, 3] >>> a.append(4) >>> a [1, 2, 3, 4]

Extending a list:

>> m = [1, 2, 3] >>> n = [4, 5] >>> m.extend(n) >>> m [1, 2, 3, 4, 5]

Removing an element:

>> a = [1, 2, 3, 2] >>> a.remove(2) >>> a [1, 3, 2]