Data structures · foundation
Array and dynamic array
An array stores elements in contiguous indexed slots; a dynamic array adds a logical length and capacity, reallocating to a larger backing array when capacity is exhausted.
Why it matters
Arrays provide fast indexed access and cache-friendly traversal, while their shifting and occasional resizing costs shape choices for insertion-heavy workloads.
Mental model
How to reason about array and dynamic array
An index is an offset from a base address, so access is direct. Appending uses the next spare slot until full, when all existing elements must be copied to a larger allocation.
Analogy
A theater row has consecutively numbered seats: seat 12 is found directly. A growing audience occasionally requires moving everyone to a larger row, but spare seats make most arrivals cheap.
Examples
See the boundary, not just the happy path
Worked example · Direct indexing
value = items[500]Given a valid index, the address is computed directly, so access is Theta(1) rather than a traversal from the start.
Worked example · Amortized append
items.append(value)Most appends fill one spare slot. Rare Theta(n) growth copies are spread across many appends, yielding amortized Theta(1).
Useful contrast · Insert near the front
items.insert(0, value)Keeping elements contiguous requires shifting the existing elements, so front insertion is Theta(n), unlike direct indexing.
Common mistakes
Misconceptions to remove early
Calling every append worst-case constant time
A growth append may copy the whole backing store. The useful guarantee is amortized constant time, not constant time for each individual call.
Assuming contiguous storage in every language list
The abstract list API does not require an array implementation. Verify the runtime's documented representation and complexity guarantees.
Quick check
Can you predict the result?
1. Why is indexing an array normally constant time?
- • The element address is computed from the base address, index, and element size
- • The runtime scans until it reaches the index
- • Every element stores a pointer to every other element
2. How can append be amortized Theta(1) if a resize costs Theta(n)?
Keep building