Dynamic Arrays and How Python Lists Really Work

The Packing Box Problem

You are moving apartments. You start with one box labeled "Books." You pack 4 books, and the box is full. You need to add a 5th book.

You have two choices:

1. Find a bigger box, move all 4 books into it, then add the 5th
2. Ask for a second box and link them somehow

Python lists use option 1 — but with a clever twist. Instead of getting a box that holds exactly 5, Python gets a box that holds 8 (roughly double). Then 9 through 16 books fit without any moving. When the 17th book arrives, Python gets a box that holds 25, moves everything, and continues.

This capacity-doubling strategy is the secret behind why Python lists feel both unlimited and fast.

Static vs Dynamic Arrays: The Core Problem

A static array has a fixed size set at creation. You declare "I need 10 slots" and you get exactly 10. If you need 11, you are stuck — you must manually allocate a new array and copy everything over.

A dynamic array handles this automatically. It maintains:

• A length — how many items are actually stored
• A capacity — how many items could be stored before a resize is needed

When length equals capacity and you try to add one more item, the dynamic array:

1. Allocates a new, larger block of memory (typically 2× the current capacity)
2. Copies all existing elements to the new block
3. Frees the old memory block
4. Adds the new element

This copying step is expensive — O(n). But because it only happens occasionally (each time the array doubles), the average cost per append remains O(1).

Watching Python Lists Grow in Real Time

Python's sys.getsizeof() reports the memory footprint of a list object in bytes. As the list grows, you can watch it resize:

import sys

lst = []
prev_size = sys.getsizeof(lst)
print(f"Empty list: {prev_size} bytes")

for i in range(26):
    lst.append(i)
    new_size = sys.getsizeof(lst)
    if new_size != prev_size:
        print(f"After {len(lst):2d} items: {new_size} bytes  ← capacity increased")
        prev_size = new_size

Sample output (exact bytes vary by Python version and platform):

Empty list: 56 bytes
After  1 items: 88 bytes  ← capacity increased
After  5 items: 120 bytes ← capacity increased
After  9 items: 184 bytes ← capacity increased
After 17 items: 248 bytes ← capacity increased
After 25 items: 312 bytes ← capacity increased

The jumps happen at 1, 5, 9, 17, 25 — this is CPython's growth formula. It is not a pure doubling, but a formula roughly equivalent to new_capacity = old_capacity + old_capacity >> 3 + (3 or 6). The result is a pattern of 0 → 4 → 8 → 16 → 25 → 35 → 46 → 58... capacity slots.

The key observation: the list does not resize on every append. Resizes cluster around specific thresholds. Between thresholds, every append is just placing an item in a pre-allocated slot — an extremely fast operation.

Why Amortized O(1) Is Real

Amortized analysis spreads the cost of expensive-but-rare operations across many cheap operations.

Think of it this way: imagine appending 16 items to an empty list that starts with capacity 4:

Total work: 16 appends + 4 copies + 8 copies = 28 operations for 16 items.

28 ÷ 16 = 1.75 operations per append on average.

As the list grows larger, the ratio approaches 1. The expensive copies become a smaller and smaller fraction of total work. This is why we say append is O(1) amortized — not always fast, but fast on average across any sequence of appends.

Amortized O(1) means: if you perform n appends, the total cost is O(n). It does not mean each individual append takes constant time.

Python List Methods and Their Big O

Every Python developer should have this table memorized. It explains countless performance bugs.

The dangerous one is x in lst. Developers frequently write:

# This is O(n) on every loop iteration → O(n²) total
for item in large_list:
    if item in another_large_list:     # DO NOT DO THIS
        process(item)

Converting another_large_list to a set makes the in check O(1), reducing the whole thing to O(n).

List Comprehensions and Performance

List comprehensions are not just syntactic sugar — they are meaningfully faster than equivalent for loops that call append.

import time

n = 1_000_000

# Method 1: for loop with append
start = time.perf_counter()
result1 = []
for i in range(n):
    result1.append(i * 2)
loop_time = time.perf_counter() - start

# Method 2: list comprehension
start = time.perf_counter()
result2 = [i * 2 for i in range(n)]
comp_time = time.perf_counter() - start

print(f"Loop:          {loop_time:.4f}s")
print(f"Comprehension: {comp_time:.4f}s")

Sample output:

Loop:          0.0821s
Comprehension: 0.0392s

The comprehension is typically 2× faster because Python avoids repeatedly looking up the append method on each iteration — the entire list-building operation runs in optimized C code internally.

Memory-Efficient Alternatives

Python lists are convenient but memory-heavy. When working with large datasets of uniform type, consider:

array module — typed arrays

import array
import sys

regular_list = list(range(10_000))
typed_array  = array.array('i', range(10_000))   # 'i' = 4-byte int

print(f"list size:  {sys.getsizeof(regular_list):,} bytes")
print(f"array size: {sys.getsizeof(typed_array):,} bytes")

Sample output:

list size:  85,176 bytes
array size: 40,056 bytes

The typed array uses roughly half the memory because it stores raw integers directly rather than Python object references.

numpy arrays — for numerical work

import numpy as np
import sys

np_array = np.array(range(10_000), dtype=np.int32)
print(f"numpy size: {np_array.nbytes:,} bytes")   # Output: 40,000 bytes

NumPy arrays are the foundation of scientific computing in Python. Operations on NumPy arrays are vectorized (run in C), making them 10–100× faster than equivalent Python loops for numerical operations.

Real Example: A Stack Built on a Python List

One of the most common uses of a dynamic array is implementing a stack — a structure where you can only push items on top and pop them from the top (Last In, First Out).

class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)     # O(1) amortized

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()     # O(1) — removes from end

    def peek(self):
        if self.is_empty():
            raise IndexError("peek at empty stack")
        return self._data[-1]       # O(1)

    def is_empty(self):
        return len(self._data) == 0 # O(1)

    def size(self):
        return len(self._data)      # O(1)

    def __repr__(self):
        return f"Stack({self._data})"

# Demo
browser_history = Stack()
browser_history.push("google.com")
browser_history.push("github.com")
browser_history.push("docs.python.org")

print(browser_history)              # Output: Stack(['google.com', 'github.com', 'docs.python.org'])
print(browser_history.peek())       # Output: docs.python.org

browser_history.pop()
print(browser_history)              # Output: Stack(['google.com', 'github.com'])
print(browser_history.size())       # Output: 2

Every operation here is O(1) because lists are optimized for end operations. This is the ideal usage pattern for a list — never inserting or deleting from the middle.

Key Takeaways

• Python lists are dynamic arrays that automatically resize by increasing capacity when full
• The doubling strategy ensures append is O(1) amortized — fast on average across any sequence of appends
• sys.getsizeof() reveals that lists allocate capacity in jumps, not one slot at a time
• End operations (append, pop(), lst[-1]) are O(1); middle/beginning operations are O(n)
• x in lst is O(n) — convert to a set when membership testing repeatedly
• List comprehensions are both more readable and faster than loop+append patterns
• For large numerical datasets, array.array or numpy arrays reduce memory usage by 50–75%

The next lesson moves into two dimensions — 2D arrays and matrices — where rows and columns let you model the real world: images, game boards, distance tables, and more.