05Module · Goodrich Ch. 5

Week 5 — Array-Based Sequences

Low-level and referential arrays, dynamic arrays, amortized analysis, and multidimensional data.

Array-Based Sequences

Python's list/tuple/str internals, dynamic resizing, amortized cost of append, and multidimensional structures.

Theory

Python lists are referential arrays — slots hold references, not raw values — giving O(1) random access.

A dynamic array doubles its capacity when full. Although a single append may cost O(n), the amortized cost is O(1).

Multidimensional data should be allocated carefully — [[0]*n]*n creates n references to the same row.

Key points

list.append is amortized O(1); list.insert(0, x) is O(n).
Tuples are immutable and use less memory than lists.
The 'accounting method' charges each append for its share of future resizing.

Code examples

Dynamic array from scratch

import ctypes

class DynamicArray:
    def __init__(self):
        self._n = 0
        self._capacity = 1
        self._A = (self._capacity * ctypes.py_object)()

    def __len__(self): return self._n

    def append(self, obj):
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        self._A[self._n] = obj
        self._n += 1

    def _resize(self, c):
        B = (c * ctypes.py_object)()
        for k in range(self._n):
            B[k] = self._A[k]
        self._A = B
        self._capacity = c

Safe 2-D matrix initialization

# WRONG — all rows are aliased
bad = [[0] * 3] * 3
bad[0][0] = 9
print(bad)  # [[9, 0, 0], [9, 0, 0], [9, 0, 0]]

# RIGHT — independent rows
good = [[0] * 3 for _ in range(3)]
good[0][0] = 9
print(good)  # [[9, 0, 0], [0, 0, 0], [0, 0, 0]]