Tuples vs Lists: Memory Allocation in Python

In Python, tuples and lists serve as sequence data types, but their underlying memory allocation differs substantially due to mutability. Because tuples are immutable, Python allocates the exact amount of memory required to store their references at creation time, alongside structural optimizations that eliminate buffer overhead. Conversely, lists are dynamic arrays designed to grow and shrink, requiring Python to over-allocate memory to maintain amortized constant-time append operations. This article explores the internal mechanisms that cause tuples to consume less memory than lists, detailing dynamic over-allocation, CPython object structures, and recycling mechanisms.

Fixed Allocation vs. Dynamic Over-Allocation

The primary driver of memory differences between lists and tuples is dynamic resizing. Because lists are mutable, they must accommodate new elements without reallocating the entire memory buffer upon every single insertion.

When you append an item to a list that has reached its capacity, CPython allocates a new, larger memory block, copies the existing pointers, and frees the old block. To keep this operation at an average time complexity of \(O(1)\), CPython over-allocates memory using a growth pattern:

\[0, 4, 8, 16, 24, 32, 40, 52, 64, 76, \dots\]

This means a list with 5 elements may hold an underlying array capable of storing 8 elements, leaving 3 slots of unused, pre-allocated memory.

Tuples cannot be modified after creation. Because their size is fixed, Python allocates memory for exactly the number of elements the tuple contains, resulting in zero unused capacity.

CPython Struct Overhead

At the C level (CPython implementation), the differences lie in how PyListObject and PyTupleObject are defined.

A list is represented as a pointer to an array of pointers:

PyListObject: Inherits standard object metadata (ob_refcnt, ob_type), an ob_size counter, a pointer (ob_item) to the dynamically allocated array of element pointers, and an integer (allocated) tracking the current buffer capacity.

A tuple integrates its element array directly into the object layout:

PyTupleObject: Inherits PyVarObject (containing ob_refcnt, ob_type, and ob_size) followed immediately by an inline array of pointers (ob_item[1]).

Because the elements are stored directly within the tuple's object structure, it avoids the separate heap allocation and the extra pointer overhead required by the list's decoupled array.

Measuring Memory Footprint

Using Python's built-in sys.getsizeof() illustrates this discrepancy directly:

import sys

empty_list = []
empty_tuple = ()

print(sys.getsizeof(empty_list))   # Outputs: 56 bytes (64-bit CPython)
print(sys.getsizeof(empty_tuple))  # Outputs: 40 bytes (64-bit CPython)

The difference becomes more pronounced as elements are added and lists over-allocate:

t = (1, 2, 3, 4, 5)
l = [1, 2, 3, 4, 5]

print(sys.getsizeof(t))  # 80 bytes
print(sys.getsizeof(l))  # 104 bytes (may be higher if built via append())

If elements are added dynamically using .append(), the list's over-allocation strategy can cause it to consume significantly more memory than a tuple holding the same number of items.

Caching and Free Lists

CPython also optimizes tuple memory through caching. To reduce the frequency of system-level memory allocation calls (malloc and free):

Singleton Empty Tuple: An empty tuple () is a singleton in CPython. Every time an empty tuple is created, Python reuses the same object in memory, meaning () is () evaluates to True. An empty list [] creates a new instance each time.
Block Free Lists: When a tuple with 1 to 20 elements is destroyed, CPython does not return its memory back to the operating system immediately. Instead, it saves the memory block into a typed free list. When a new tuple of that exact size is instantiated, Python reuses that pre-allocated memory block, minimizing allocation overhead. While lists also maintain a free list of PyListObject structs, their underlying item arrays must still be reallocated when sizes differ.