What a dynamic array is
A dynamic array stores elements in a single contiguous block of memory, just like a fixed array, but it can grow. It tracks two numbers: the size (how many elements are stored) and the capacity (how many slots the block can hold).
The cost of appending
When you append and there is spare capacity, the element drops into the next free slot cheaply. The trouble comes when the block is full. The array must:
- Allocate a bigger block.
- Copy every existing element into it.
- Free the old block.
Why doubling matters
If you grew the capacity by just one slot each time it filled, every append would copy everything, and the total work would balloon. Instead, real implementations double the capacity when full.
Because capacity doubles, expensive copies happen rarely and ever further apart. Spread across many appends, the average cost per append stays constant, even though a single append occasionally pays a large copy. This averaged view is called amortized cost.
Key idea
A dynamic array doubles its capacity when full so copies grow rare, giving appends a constant average cost despite occasional expensive resizes.