Arrays & Dynamic Arrays

The problem: find item 700,000 instantly

Suppose you store a million sensor readings and someone asks for reading number 700,000. If the readings were scattered around memory with each one pointing to the next, you would have to walk 700,000 steps. With an array, you compute where reading 700,000 lives with one multiplication and one addition, and jump straight there. That is the whole idea: position determines address.

Every access takes about the same time. Position 0 and position 999,999 are equally easy to reach. Hold onto that fact; the rest of the module explains why it is true and what it costs.

Contiguous memory and the indexing formula

Computer memory is a giant numbered sequence of bytes. Each byte has an address, an integer. An array reserves one unbroken (contiguous) run of addresses and divides it into slots of equal size. If the array starts at address base and each slot is size bytes wide, then slot i starts at

address(i) = base + i × size

That is one multiply and one add, whatever i is: O(1). It is also why indexes start at 0: index 0 is the base address itself, with offset zero.

Two requirements make the formula work: the slots must be equal size and the memory must be contiguous. Keep both in mind; they explain both the strengths (fast indexing, great cache behaviour) and the weaknesses (inserting in the middle means shifting, growing means moving) of arrays.

Static vs dynamic arrays

A static array has a fixed capacity chosen when it is created. In C, int a[10]; is ten ints, forever. You cannot append an eleventh: the memory right after the array may already belong to something else.

A dynamic array (also called a growable array, resizable array, or vector) hides that limit. It keeps a static array internally, plus two numbers:

• size (or length): how many slots are in use;
• capacity: how many slots the internal array has.

Appending writes into slot size and increments it, as long as size < capacity. When the array is full, it resizes: allocate a bigger static array, copy every element across, release the old one. That copy is O(n), but as you proved in M19, growing by a constant factor makes it rare enough that appends are amortized O(1).

How CPython's list really works

A Python list can hold anything: [1, "two", 3.0, None]. But an array needs equal-sized slots, and a string is not the same size as an integer. CPython's solution: the list does not store the objects themselves. It stores pointers to them. Every pointer is 8 bytes on a 64-bit machine, so the slots are equal-sized even though the objects are not.

In C, CPython's list object (PyListObject) looks roughly like this:

# Simplified view of Include/cpython/listobject.h
# typedef struct {
#     PyObject_VAR_HEAD          /* reference count, type pointer, ob_size (the length) */
#     PyObject **ob_item;        /* pointer to a C array of PyObject* pointers */
#     Py_ssize_t allocated;      /* capacity: number of slots in ob_item */
# } PyListObject;

Consequences you can now explain:

• sys.getsizeof(a_list) counts the header plus the pointer array, not the objects pointed to.
• Two lists can share the same objects, which is why copying a list is "shallow" (M06).
• A list of a million floats costs 8 bytes per pointer plus 24 bytes per float object: about four times more than a packed array of doubles. This is why array.array and NumPy exist.

Over-allocation

When an append needs more room, CPython's list_resize computes the new capacity roughly as

new_allocated = (newsize + (newsize >> 3) + 6) & ~3   # about 1.125 × newsize, rounded to a multiple of 4

That is a growth factor of about 1.125, much gentler than doubling. Less memory is wasted, at the price of more frequent resizes; amortized append is still O(1) because growth is still proportional. The capacities you will see are 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, …

What each operation costs, and why

Inserting at index i must make a gap, and in a contiguous block the only way to make a gap is to move everything after it. Insert at the front, and every element moves.

Building a DynamicArray

Let's build our own dynamic array. To keep things honest we will pretend Python only gives us a fixed-size block: we create storage with [None] * capacity and then only index into it, never calling append, insert, or slicing on it. That simulates a C static array.

class DynamicArray:
    def __init__(self):
        self._size = 0                       # slots in use
        self._capacity = 1                   # slots allocated
        self._data = [None] * self._capacity # our "static array"

    def __len__(self):
        return self._size

    @property
    def capacity(self):
        return self._capacity

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):          # the O(n) copy
            new_data[i] = self._data[i]
        self._data = new_data
        self._capacity = new_capacity

The special methods you met in M11 make it feel built-in: __len__ for len(), __getitem__ for a[i], __iter__ for for loops. The exercises in Practice build the rest step by step: indexing with negative indexes, append with resizing, insert with shifting, and remove.

Typed arrays: the array module

When every element is the same primitive type, storing pointers to separate objects is wasteful. The standard library's array.array stores raw machine values directly in a contiguous buffer, like a C array, while still growing like a list. You pick a typecode:

Typed arrays enforce the type and range of every value, support append, extend, slicing, and tobytes()/frombytes() for fast binary I/O. Reading an element creates a fresh Python object ("boxing"), so element-by-element Python loops are not faster than with a list; the win is memory and I/O. For fast arithmetic over whole arrays you want NumPy.

Bytes and bytearray

bytes is an immutable array of integers 0–255, one byte each: exactly how files, network packets, and images are stored. bytearray is its mutable twin, a dynamic array of bytes.

memoryview and the buffer protocol

Slicing a bytes or bytearray copies the data: O(k) time and memory. For big binary data (a 500 MB video frame, a network buffer) that is wasteful. The buffer protocol is a C-level agreement that lets objects such as bytes, bytearray, array.array, and NumPy arrays expose their raw memory directly. A memoryview is a Python window onto such memory: slicing a memoryview creates another view, without copying.

Professional uses include parsing binary file formats without copying, reading into a pre-allocated buffer with file.readinto(view) or socket.recv_into(view), and handing data between libraries (Pillow, NumPy, PyArrow) without conversion. While a memoryview exists, the underlying bytearray cannot be resized, because resizing could move the memory out from under the view.

2-D lists and the [[0] * n] * m bug

A grid is naturally a list of rows, each row a list. The tempting way to build one is a classic bug:

Both rows change. [0] * 3 creates one row list; multiplying the outer list by 2 copies the pointer to that row, not the row. So grid[0] and grid[1] are the same object. Remember: lists store pointers, and * repeats pointers.

The fix is a comprehension, which evaluates [0] * 3 afresh for every row. [0] * 3 itself is fine because integers are immutable: sharing the same 0 object is harmless, since you can only replace a slot, not mutate the 0.

rows, cols = 3, 4
grid = [[0] * cols for _ in range(rows)]   # correct
grid[r][c]                                 # row r, column c
column_2 = [row[2] for row in grid]       # columns need a loop
transposed = [list(col) for col in zip(*grid)]

A list of lists is not a contiguous 2-D array: each row is a separate list somewhere on the heap. For a true contiguous grid, you would store a flat list of rows * cols items and compute index = r * cols + c, which is exactly what NumPy does internally ("row-major order").

Preview: NumPy arrays

NumPy's ndarray combines everything in this module: a contiguous typed buffer (like array.array), a shape and strides for multi-dimensional indexing (the r * cols + c formula, generalised), the buffer protocol, and vectorised operations that loop in C instead of Python.

The strides (32, 8) say "move 32 bytes for the next row, 8 bytes for the next column": the address formula in two dimensions. You will study NumPy properly in M48.

Pitfalls and when to use what

• Front operations on lists. insert(0, x) and pop(0) in a loop are O(n²) overall. Use collections.deque.
• Membership tests in loops. x in a_list is O(n). Use a set.
• Building strings or lists by repeated concatenation. a = a + [x] copies every time (O(n²) overall); use append, extend, or "".join.
• Modifying a list while iterating over it. Removing items shifts the rest, so the loop skips elements. Iterate over a copy or build a new list.
• Aliased rows. [[0] * n] * m.

Interview classics on arrays

Many interview problems are array problems in disguise: rotate an array in place, move zeros to the end, find the maximum subarray sum (Kadane's algorithm), merge two sorted arrays, and two-pointer and sliding-window problems. You will practise these techniques in M30 and M35.

Practice: build DynamicArray

Each exercise adds to the same class. The starter code contains the parts you have already built. Remember the rule: treat self._data as a fixed-size block. Only read or assign self._data[i]; never call list methods on it.

class DynamicArray:
    def __init__(self, items=()):
        self._capacity = max(1, len(items))
        self._data = [None] * self._capacity
        self._size = 0
        for x in items:
            self._data[self._size] = x
            self._size += 1

    def __len__(self):
        return self._size

    def _normalize(self, index):
        if index < 0:
            index += self._size
        if not 0 <= index < self._size:
            raise IndexError("DynamicArray index out of range")
        return index

    def __getitem__(self, index):
        return self._data[self._normalize(index)]

    def __setitem__(self, index, value):
        self._data[self._normalize(index)] = value

class DynamicArray:
    def __init__(self):
        self._capacity = 1
        self._data = [None] * self._capacity
        self._size = 0
        self.copies = 0

    def __len__(self):
        return self._size

    @property
    def capacity(self):
        return self._capacity

    def __getitem__(self, index):
        if index < 0:
            index += self._size
        if not 0 <= index < self._size:
            raise IndexError("DynamicArray index out of range")
        return self._data[index]

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
            self.copies += 1
        self._data = new_data
        self._capacity = new_capacity

    def append(self, value):
        if self._size == self._capacity:
            self._resize(2 * self._capacity)
        self._data[self._size] = value
        self._size += 1

class DynamicArray:
    def __init__(self):
        self._capacity = 1
        self._data = [None] * self._capacity
        self._size = 0

    def __len__(self):
        return self._size

    def __iter__(self):
        for i in range(self._size):
            yield self._data[i]

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data, self._capacity = new_data, new_capacity

    def append(self, value):
        if self._size == self._capacity:
            self._resize(2 * self._capacity)
        self._data[self._size] = value
        self._size += 1

    def insert(self, index, value):
        if index < 0:
            index = max(0, index + self._size)
        index = min(index, self._size)
        if self._size == self._capacity:
            self._resize(2 * self._capacity)
        for i in range(self._size, index, -1):
            self._data[i] = self._data[i - 1]
        self._data[index] = value
        self._size += 1

class DynamicArray:
    def __init__(self, items=()):
        self._capacity = max(1, len(items))
        self._data = [None] * self._capacity
        self._size = 0
        for x in items:
            self._data[self._size] = x
            self._size += 1

    def __len__(self):
        return self._size

    def __iter__(self):
        for i in range(self._size):
            yield self._data[i]

    def _resize(self, new_capacity):
        new_data = [None] * new_capacity
        for i in range(self._size):
            new_data[i] = self._data[i]
        self._data, self._capacity = new_data, new_capacity

    def _delete_at(self, i):
        item = self._data[i]
        for j in range(i, self._size - 1):
            self._data[j] = self._data[j + 1]
        self._data[self._size - 1] = None
        self._size -= 1
        if self._capacity > 1 and self._size <= self._capacity // 4:
            self._resize(max(1, self._capacity // 2))
        return item

    def pop(self, index=-1):
        if index < 0:
            index += self._size
        if not 0 <= index < self._size:
            raise IndexError("pop index out of range")
        return self._delete_at(index)

    def remove(self, value):
        for i in range(self._size):
            if self._data[i] == value:
                self._delete_at(i)
                return
        raise ValueError(f"{value!r} not in DynamicArray")

class Grid:
    def __init__(self, rows, cols, fill=0):
        self.rows = rows
        self.cols = cols
        self.cells = [fill] * (rows * cols)

    def _index(self, key):
        r, c = key
        if not (0 <= r < self.rows and 0 <= c < self.cols):
            raise IndexError(f"cell {key} out of range")
        return r * self.cols + c

    def __getitem__(self, key):
        return self.cells[self._index(key)]

    def __setitem__(self, key, value):
        self.cells[self._index(key)] = value

    def row(self, r):
        return self.cells[r * self.cols:(r + 1) * self.cols]

    def column(self, c):
        return self.cells[c::self.cols]

    def transpose(self):
        t = Grid(self.cols, self.rows)
        for r in range(self.rows):
            for c in range(self.cols):
                t[c, r] = self[r, c]
        return t

Mini-project: a ring-buffer log

pixi init ringlog
cd ringlog
pixi add python=3.14 pytest
pixi run python -m pytest -q

Quiz

Recap

• An array is contiguous, equal-sized slots: address = base + index × size, so indexing is O(1).
• A dynamic array is a static array plus size and capacity; it resizes by a factor, making append amortized O(1).
• CPython's list is a dynamic array of PyObject* pointers growing by about 1.125×.
• Insert and delete shift everything after the position: O(n − i). Front operations are O(n).
• array.array stores raw typed values compactly; bytes/bytearray are byte arrays.
• memoryview gives zero-copy slices of any buffer-protocol object.
• Build grids with a comprehension; [[0] * n] * m aliases rows.

Going further

• array: efficient arrays of numeric values
• Binary sequence types: bytes, bytearray, memoryview
• The buffer protocol (C API)
• Design FAQ: how are lists implemented in CPython?
• Next: M21 Linked Lists, the structure that trades O(1) indexing for O(1) insertion.