Linear structures and hashing · 08 / 53
Static/dynamic arrays and cache locality
Understand → trace → implement → justify
1 min reading · allow extra time for practiceArrays translate indexing into base+i·elementSize under a fixed-width representation and valid bounds. Python lists are dynamic arrays of references, not contiguous copies of every referenced object.
Middle insertions and deletions shift following elements. Appending is cheap with spare capacity but resizing allocates and copies. Size counts used slots; capacity counts allocated slots. Separate growth and shrink thresholds to avoid thrashing.
Sequential scanning benefits cache locality and prefetching. Linked-list O(1) insertion assumes the insertion location is already known; locating it may cost O(n). Prefer arrays for frequent indexed access and evaluate lists for edits around known nodes. Learn the actual contracts of your language's collections.
A worked trace
Insert 15 at index 1 into [10,20,30,40]: shift 40,30,20 right, yielding [10,15,20,30,40].
Cost and assumptions
Indexing O(1), scan Θ(n), middle insertion Θ(n), append amortised O(1).
Executable example
Run with Python 3. Assertions check a small example; they do not constitute a general correctness proof. Some advanced examples are explicitly small models or reference oracles, not full production implementations.
a = [10, 20, 30, 40]
a.insert(1, 15)
assert a == [10, 15, 20, 30, 40]
# Repeated pop(0) shifts the remaining references.TEST YOUR UNDERSTANDING
Your turn
What is the total cost of emptying a list with repeated pop(0)?
Reveal the reasoning
(n−1)+(n−2)+…+0 shifts ⇒ Θ(n²). Use deque.popleft for FIFO.
Take it further
- Write down the input contract and the invariant before changing the example.
- Add empty, boundary, duplicate and adversarial cases where they are relevant. Compare with a simple oracle.
- Derive the cost under the stated model; measure several input sizes and explain discrepancies.
Primary reading & lecture notes
Original explanations in this course; these references provide proofs and further reading. Source links may cover the broader module.
Pat Morin · Open Data Structures ↗