Lists and Dynamic Array Mechanics

Updated

September 7, 2026

Lists and Dynamic Array Mechanics

After reading this chapter, you will master the internal memory layout of Python lists, analyze how CPython achieves amortized \(O(1)\) appends via over-allocation, benchmark in-place mutations against full-copy allocations, implement custom sort keys, and avoid reference duplication pitfalls in multi-dimensional lists.

Mental model

A Python list is not a linked list; it is a dynamic array of pointers (PyListObject in CPython). The list structure holds an array of 8-byte memory addresses (on 64-bit systems) pointing to arbitrary objects located elsewhere on the heap:

CPython PyListObject Architecture:
┌────────────────────────────────────────────────────────┐
│ PyListObject Header (56 bytes on 64-bit)               │
│  ├── ob_refcnt: 1                                      │
│  ├── ob_type:   &PyList_Type                           │
│  ├── ob_size:   3   (Logical element count)            │
│  ├── allocated: 6   (Physical buffer capacity slots)   │
│  └── ob_item    ───────────────────────────┐           │
└────────────────────────────────────────────┼───────────┘
                                             │
      ┌──────────────────────────────────────┘
      ▼
┌───────────┬───────────┬───────────┬───────────┬───────────┬───────────┐
│ Slot 0    │ Slot 1    │ Slot 2    │ Slot 3    │ Slot 4    │ Slot 5    │
│ &"web-01" │ &"web-02" │ &"db-01"  │ NULL      │ NULL      │ NULL      │
└─────┬─────┴─────┬─────┴─────┬─────┴───────────┴───────────┴───────────┘
      │           │           │
      ▼           ▼           ▼
   "web-01"    "web-02"    "db-01"

To prevent reallocating the memory buffer on every single append(), CPython over-allocates spare slots using a geometric growth formula (allocated = size + (size >> 3) + (size < 9 ? 3 : 6)).

This yields distinct algorithmic complexities: - Append / Pop at end: Amortized \(O(1)\) — fast pointer write into pre-allocated slot. - Insert / Delete at index 0: \(O(N)\) — every existing pointer must be shifted in memory with memmove. - Random index lookup (data[i]): \(O(1)\) — direct pointer offset calculation.

Minimal example

Save as list_mechanics.py:

# list_mechanics.py
import sys

def trace_list_growth() -> None:
    """Trace CPython dynamic array reallocation steps as elements are appended."""
    items: list[int] = []
    prev_bytes = sys.getsizeof(items)
    print(f"Initial empty list size: {prev_bytes} bytes")

    print("\nTracing capacity reallocations up to 30 items:")
    for i in range(1, 31):
        items.append(i)
        curr_bytes = sys.getsizeof(items)
        if curr_bytes != prev_bytes:
            # On 64-bit CPython, base struct is 56 bytes, each pointer is 8 bytes
            capacity = (curr_bytes - 56) // 8
            print(f"  Length: {len(items):2d} | Memory: {curr_bytes:3d} bytes | Allocated slots: {capacity:2d}")
            prev_bytes = curr_bytes

def main() -> None:
    trace_list_growth()

if __name__ == "__main__":
    main()

Run via uv run python list_mechanics.py:

Initial empty list size: 56 bytes

Tracing capacity reallocations up to 30 items:
  Length:  1 | Memory:  88 bytes | Allocated slots:  4
  Length:  5 | Memory: 120 bytes | Allocated slots:  8
  Length:  9 | Memory: 184 bytes | Allocated slots: 16
  Length: 17 | Memory: 248 bytes | Allocated slots: 24
  Length: 25 | Memory: 312 bytes | Allocated slots: 32

Worked examples

Case 1: In-Place Mutations vs Full Copy Allocations

When working with large collections, choosing between mutating in place (extend, append, +=) versus constructing new lists (+) determines whether memory usage is \(O(1)\) or \(O(N)\):

# list_mutations.py
import time

def benchmark_concatenation() -> None:
    n = 20_000

    # Approach A: Repeated concatenation with + (Creates a brand new list every iteration!)
    start = time.perf_counter()
    result_a = []
    for i in range(n):
        result_a = result_a + [i]
    dur_a = time.perf_counter() - start

    # Approach B: In-place mutation with append (Leverages pre-allocated spare slots)
    start = time.perf_counter()
    result_b = []
    for i in range(n):
        result_b.append(i)
    dur_b = time.perf_counter() - start

    # Approach C: Batch extension with extend
    start = time.perf_counter()
    result_c = []
    result_c.extend(range(n))
    dur_c = time.perf_counter() - start

    print(f"Repeated '+' concat (allocates N lists): {dur_a:.5f}s")
    print(f"Repeated append()  (amortized O(1)):     {dur_b:.5f}s  ({dur_a / dur_b:.1f}x faster)")
    print(f"Single extend()    (bulk C allocation):   {dur_c:.5f}s  ({dur_a / dur_c:.1f}x faster)")

def main() -> None:
    benchmark_concatenation()

if __name__ == "__main__":
    main()

Run:

uv run python list_mutations.py

Output:

Repeated '+' concat (allocates N lists): 0.04612s
Repeated append()  (amortized O(1)):     0.00068s  (67.8x faster)
Single extend()    (bulk C allocation):   0.00014s  (329.4x faster)

Case 2: Custom In-Place Sorting with Timsort

Python’s list.sort() implements Timsort (and adaptive Powersort heuristics in Python 3.11+). It sorts strictly in place with \(O(N \log N)\) worst-case guarantees and \(O(N)\) for pre-sorted inputs:

# list_sorting.py
def main() -> None:
    servers = [
        {"host": "srv-03", "cpu_percent": 88.5, "rack": "R2"},
        {"host": "srv-01", "cpu_percent": 12.0, "rack": "R1"},
        {"host": "srv-04", "cpu_percent": 95.2, "rack": "R2"},
        {"host": "srv-02", "cpu_percent": 45.0, "rack": "R1"},
    ]

    # 1. In-place sort by CPU load descending
    servers.sort(key=lambda s: s["cpu_percent"], reverse=True)
    print("--- Sorted by Highest CPU Load (In-Place) ---")
    for s in servers:
        print(f"  {s['host']} | CPU: {s['cpu_percent']:5.1f}% | Rack: {s['rack']}")

    # 2. Multi-criterion sorting using tuples: Rack ascending, then CPU descending
    # Notice: negation (-s['cpu_percent']) allows descending numeric order within a tuple key!
    servers.sort(key=lambda s: (s["rack"], -s["cpu_percent"]))
    print("\n--- Multi-Key Sort (Rack ASC, CPU DESC) ---")
    for s in servers:
        print(f"  Rack: {s['rack']} | {s['host']} | CPU: {s['cpu_percent']:5.1f}%")

if __name__ == "__main__":
    main()

Run:

uv run python list_sorting.py

Output:

--- Sorted by Highest CPU Load (In-Place) ---
  srv-04 | CPU:  95.2% | Rack: R2
  srv-03 | CPU:  88.5% | Rack: R2
  srv-02 | CPU:  45.0% | Rack: R1
  srv-01 | CPU:  12.0% | Rack: R1

--- Multi-Key Sort (Rack ASC, CPU DESC) ---
  Rack: R1 | srv-02 | CPU:  45.0%
  Rack: R1 | srv-01 | CPU:  12.0%
  Rack: R2 | srv-04 | CPU:  95.2%
  Rack: R2 | srv-03 | CPU:  88.5%

Case 3: Shallow Copies vs Deep Copies

Because lists store object references, copying a list requires understanding the boundary between shallow copies (duplicating the pointer array) and deep copies (recursively duplicating referenced objects):

# list_copying.py
import copy

def main() -> None:
    original = [
        {"node": "worker-1", "status": "active"},
        {"node": "worker-2", "status": "active"},
    ]

    # 1. Shallow copy: new list container, but points to identical inner dictionaries!
    shallow = original.copy()

    # 2. Deep copy: completely independent object graph
    deep = copy.deepcopy(original)

    # Mutate inner dictionary in shallow copy
    shallow[0]["status"] = "OFFLINE"

    print("After modifying shallow[0]['status'] = 'OFFLINE':")
    print(f"  Original node 1 status: {original[0]['status']}  <-- UNINTENTIONALLY MUTATED!")
    print(f"  Shallow  node 1 status: {shallow[0]['status']}")
    print(f"  Deep     node 1 status: {deep[0]['status']}     <-- Completely isolated")

if __name__ == "__main__":
    main()

Run:

uv run python list_copying.py

Output:

After modifying shallow[0]['status'] = 'OFFLINE':
  Original node 1 status: OFFLINE  <-- UNINTENTIONALLY MUTATED!
  Shallow  node 1 status: OFFLINE
  Deep     node 1 status: active     <-- Completely isolated

Pitfalls

Pitfall 1: Modifying a List While Iterating Over It

Never add or remove elements from a list while iterating over it directly. The loop maintains an internal integer index counter, causing elements to be silently skipped:

# THE TRAP: Silently skips items
numbers = [1, 2, 2, 3, 4, 2, 5]
for x in numbers:
    if x == 2:
        numbers.remove(x)  # BUG: Modifies array while index advances!
print(f"Result with bug: {numbers}")  # Still contains [1, 2, 3, 4, 5]!

# THE FIX: Iterate over a slice copy or use a list comprehension
numbers = [1, 2, 2, 3, 4, 2, 5]
numbers = [x for x in numbers if x != 2]
print(f"Clean result:    {numbers}")  # [1, 3, 4, 5]

Pitfall 2: The Repeated Multiplication Reference Duplication Bug

Using the * operator on a list containing a mutable object duplicates the same reference, not independent copies:

# THE TRAP: 3 rows pointing to the identical list object!
grid = [[0] * 3] * 3
grid[0][0] = 99
print("Buggy grid:")
for row in grid:
    print(f"  {row}")  # All 3 rows now have 99 at index 0!

Output:

Buggy grid:
  [99, 0, 0]
  [99, 0, 0]
  [99, 0, 0]

# THE FIX: Use a list comprehension to allocate distinct inner lists
safe_grid = [[0] * 3 for _ in range(3)]
safe_grid[0][0] = 99
print("\nSafe grid:")
for row in safe_grid:
    print(f"  {row}")

Output:

Safe grid:
  [99, 0, 0]
  [0, 0, 0]
  [0, 0, 0]

Pitfall 3: Assuming `list.sort()` Returns the Sorted List

list.sort() modifies the array in place and returns None by design to prevent confusing in-place mutation with copy allocation:

# THE TRAP:
data = [5, 2, 8, 1]
data = data.sort()  # BUG: data is now None!
print(f"data is: {data}")

# THE FIX:
# Either call sort() as a statement:
data = [5, 2, 8, 1]
data.sort()

# Or use sorted() if you want a new returned list:
other = [5, 2, 8, 1]
result = sorted(other)

Exercises

Initialize an empty list and print its size in bytes using sys.getsizeof(). Append 100 elements one by one, recording each logical length where reallocation occurs.
Given a list of user dictionaries [{"name": "Alice", "age": 30}, {"name": "Bob", "age": 25}], use list.sort() with a lambda key to sort them in ascending order of age in place.
Benchmark the time difference between list.pop(0) (which shifts all elements) and list.pop() (which takes the tail element) on a list of 100,000 integers.
Construct a 4x4 coordinate board filled with "." using a safe list comprehension. Verify that modifying board [1][2] changes only that single cell.
Given two lists a = [1, 2, 3] and b = [4, 5, 6], explain the memory difference between a.extend(b) and a = a + b.

Lists and Dynamic Array Mechanics

Mental model

Minimal example

Worked examples

Case 1: In-Place Mutations vs Full Copy Allocations

Case 2: Custom In-Place Sorting with Timsort

Case 3: Shallow Copies vs Deep Copies

Pitfalls

Pitfall 1: Modifying a List While Iterating Over It

Pitfall 2: The Repeated Multiplication Reference Duplication Bug

Pitfall 3: Assuming list.sort() Returns the Sorted List

Exercises

Further reading

Pitfall 3: Assuming `list.sort()` Returns the Sorted List