A growable block of memory
A dynamic array stores elements in one contiguous block, like a fixed array, but it can grow. It tracks two numbers: the size, how many elements are stored, and the capacity, how many fit before a resize is needed. Reading or writing any index is fast because the address is computed directly from the base pointer.
What happens when it fills up
When you append and the size already equals the capacity, the array is full. The structure then:
- Allocates a brand new, larger block.
- Copies every existing element into it.
- Frees the old block and continues.
That copy touches every element, so a single full append is expensive. The trick is how much to grow.
Doubling keeps it cheap
If the array grows by a fixed amount each time, copies pile up and appends become slow on average. Instead, implementations multiply the capacity, usually doubling it. Because expensive resizes happen exponentially less often, the average cost of an append stays constant even though some appends are pricey. This averaged-over-many-operations view is called amortized analysis.
Key idea
A dynamic array gives fast indexed access by storing elements contiguously, and by doubling capacity on overflow it keeps the amortized cost of appending constant.