Collections

Python lists are ordered, mutable sequences of arbitrary objects. They are the most frequently Used built-in container and serve as the default sequence type for most tasks.

CPython implements list as a contiguous array of pointers (specifically, a C array of PyObject*). This is a critical design decision with direct consequences for performance Characteristics.

graph LR
    subgraph "list object on heap"
        ob_refcnt["ob_refcnt"]
        ob_type["ob_type"]
        ob_size["ob_size (length)"]
        allocated["allocated (capacity)"]
        items["items[0] | items[1] | items[2] | ... | items[allocated-1]"]
    end

    subgraph "heap objects"
        obj0["PyObject<br/>"int: 42'"]
        obj1["PyObject<br/>'str: hello'"]
        obj2["PyObject<br/>'list: [1,2]'"]
    end

    items --> obj0
    items --> obj1
    items --> obj2

Each items[i] slot is a pointer to a heap-allocated PyObject. The list itself does not store the Objects inline — it stores references. This means:

1. A list of three integers occupies three pointer slots (24 bytes on 64-bit) plus three separate heap allocations for the integer objects.
2. Appending to a list never copies the contained objects. Only pointers are moved.
3. A single object can appear in multiple lists simultaneously without duplication.

When list.append() runs and the internal array is full, CPython must allocate a new, larger array And copy all existing pointers into it. The growth strategy determines how much larger the new array Is.

graph TD
    A["append(x) called"] --> B{"ob_size == allocated?"}
    B -- No --> C["items[ob_size] = x<br/>ob_size += 1"]
    C --> D["return"]
    B -- Yes --> E["new_allocated = grow(allocated)"]
    E --> F["malloc new array<br/>of size new_allocated"]
    F --> G["memcpy old pointers<br/>to new array"]
    G --> H["free old array"]
    H --> C

The growth formula (from CPython source, Objects/listobject.c) is:

new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)

Roughly, this means the new capacity is approximately newsize + newsize/8 + 6. This is a geometric growth factor of about 1.125x (9/8), which is deliberately smaller than the 2x factor Used by many other languages. The Python developers chose this because:

• Lists are frequently used for temporary accumulations where the final size is not much larger than the initial size. A 2x factor wastes more memory in these cases.
• The smaller factor still guarantees amortized O(1) append.

Amortized analysis. Consider n appends to an initially empty list. A resize occurs when the list Hits sizes that trigger reallocation. The total number of pointer copies across all resizes is Bounded by a geometric series that converges to O(n). Therefore, the average cost per append is O(1), even though any single append may cost O(n).

import sys

lst = []
print(sys.getsizeof(lst))  # 56 bytes (empty list)

for i in range(10):
    lst.append(i)
    print(f"len={len(lst)}, sizeof={sys.getsizeof(lst)}")

## Output pattern on 64-bit CPython:
## len=0,  sizeof=56   (empty, 0 slots)
# len=1,  sizeof=88   (4 slots allocated)
# len=2,  sizeof=88   (4 slots)
# len=3,  sizeof=88   (4 slots)
# len=4,  sizeof=88   (4 slots, now full)
# len=5,  sizeof=120  (8 slots allocated -- grew)
# len=6,  sizeof=120  (8 slots)
# len=7,  sizeof=120  (8 slots)
# len=8,  sizeof=120  (8 slots, now full)
# len=9,  sizeof=184  (16 slots allocated -- grew)
# len=10, sizeof=184  (16 slots)

lst = [3, 1, 4, 1, 5, 9]

# Mutation
lst.append(2)        # [3, 1, 4, 1, 5, 9, 2]
lst.extend([6, 5])   # [3, 1, 4, 1, 5, 9, 2, 6, 5]
lst.insert(0, 99)    # [99, 3, 1, 4, 1, 5, 9, 2, 6, 5]
lst.pop()            # 5, lst = [99, 3, 1, 4, 1, 5, 9, 2, 6]
lst.pop(0)           # 99, lst = [3, 1, 4, 1, 5, 9, 2, 6]
lst.remove(1)        # removes first 1, lst = [3, 4, 1, 5, 9, 2, 6]
lst.reverse()        # [6, 2, 9, 5, 1, 4, 3]
lst.sort()           # [1, 2, 3, 4, 5, 6, 9]
lst.clear()          # []

# Non-mutating
lst = [3, 1, 4, 1, 5]
lst.index(4)         # 2
lst.count(1)         # 2
lst.copy()           # shallow copy [3, 1, 4, 1, 5]

Slicing creates a new list containing copies of the pointer slots in the specified range. It Does not copy the referenced objects.

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# lst[start:stop:step]
lst[2:5]       # [2, 3, 4]
lst[:3]        # [0, 1, 2]
lst[7:]        # [7, 8, 9]
lst[::2]       # [0, 2, 4, 6, 8]
lst[::-1]      # [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
lst[1::2]      # [1, 3, 5, 7, 9]
lst[-3:]       # [7, 8, 9]
lst[-5:-2]     # [5, 6, 7]

# Slice assignment (modifies in place)
lst[2:5] = [20, 30, 40]  # [0, 1, 20, 30, 40, 5, 6, 7, 8, 9]
lst[1:1] = [10, 11]      # insert without replacing: [0, 10, 11, 1, 20, ...]
del lst[2:4]              # delete slice

Slicing has O(k) time complexity where k is the size of the slice. The step parameter is handled Internally by a loop that strides through the source array, so lst[::2] is O(n/2) = O(n).

List comprehensions are both more concise and faster than equivalent for loops because they run at C speed inside the CPython interpreter loop.

# List comprehension
squares = [x**2 for x in range(10)]

# Equivalent for loop (slower -- Python bytecode per iteration)
squares = []
for x in range(10):
    squares.append(x**2)

# With condition
even_squares = [x**2 for x in range(10) if x % 2 == 0]

# Nested (flattening a matrix)
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
flat = [x for row in matrix for x in row]  # [1, 2, 3, 4, 5, 6, 7, 8, 9]