Dynamic arrays
Fixed-size arrays cannot grow. Dynamic arrays, such as Python lists, Java's ArrayList, and C++'s std::vector, grow automatically while keeping fast indexing, using a clever doubling strategy.
The problem
A static array has a fixed capacity chosen when it is created. If you do not know how many items you will have, you need a structure that grows. Allocating a much larger array up front wastes memory; growing by one slot each time is painfully slow.
How dynamic arrays work
A dynamic array keeps an underlying static array with some spare capacity and tracks its size, the number of slots actually used. Appending writes into the next free slot in O(1). When the array is full, it allocates a new, larger block, typically double the capacity, copies every element across, and frees the old block.
Why doubling works: amortised analysis
A resize copies n elements, which is expensive, but it happens rarely. Starting from capacity 1 and doubling, appending n items triggers copies of 1 + 2 + 4 + ... + n/2 elements, fewer than n in total. So n appends cost under 3n operations overall: O(1) amortised per append, even though an individual append can occasionally cost O(n).
Why not grow by a constant
If the array grew by a fixed 10 slots each time, appending n items would trigger about n/10 resizes copying 10, 20, 30, ... elements, totalling roughly n^2/20 copies: O(n) amortised per append, quadratic overall. Geometric growth, by any factor greater than 1, is essential; real implementations use factors between about 1.125 and 2.
Shrinking
Some implementations also shrink when many elements are removed, but care is needed. If an array halves whenever it is half full and doubles whenever full, alternating inserts and deletes at the boundary could cause a resize on every operation. A safer rule is to halve only when the array falls to a quarter full.
Costs summary
Dynamic arrays give O(1) indexing, O(1) amortised append and pop at the end, and O(n) insertion or deletion elsewhere because of shifting. Their memory is contiguous, so iteration is fast. The cost of a resize spike can matter in real-time systems, which may pre-allocate capacity with methods such as reserve in C++ or ensureCapacity in Java.
References and invalidation
Because resizing moves elements to new memory, pointers or iterators into the old block become invalid. In C++, holding a pointer to a vector element and then calling push_back can leave a dangling pointer, a subtle bug. Languages with garbage collection and references avoid the crash but the general lesson remains: do not hold positions into a structure that may reorganise itself.
Worked example
Appending 9 items to an empty dynamic array with initial capacity 1 that doubles: resizes happen when the 2nd, 3rd, 5th, and 9th items arrive, growing capacity to 2, 4, 8, and 16 and copying 1, 2, 4, and 8 elements: 15 copies. Add the 9 writes and the total is 24 operations for 9 appends, under 3 per append, consistent with O(1) amortised cost.
Key takeaways
Dynamic arrays wrap a static array with spare capacity, tracking size and capacity. Appends are O(1) except when full, when the array grows by a constant factor, often 2, copying elements. Amortised analysis shows n appends cost O(n) total: O(1) per append. Constant-increment growth gives quadratic total cost. Shrink only at a quarter full to avoid thrashing. Indexing is O(1); middle insertion is O(n). Resizing invalidates pointers and iterators.
Flashcard
Resizable array with spare capacity
Check your understanding
A dynamic array doubles when full. What is the amortised cost of an append?