Dynamic Array
A resizable array: contiguous storage with a size and a capacity. Appends are O(1) amortised — when full, it allocates double the capacity and copies everything over.
A dynamic array (Python list, Java ArrayList, C++ vector, JS array) keeps elements contiguous in memory, which gives O(1) indexing and excellent cache behaviour. It tracks two numbers: size (elements stored) and capacity (slots allocated).
Appending into spare capacity is a single write. When size hits capacity, the array allocates a new block — typically 2× larger — and copies every element across. That copy is O(n), but doubling means it happens so rarely that the average append is still O(1): n appends cost at most ~2n copies total. This is the classic amortised-analysis example.
Inserting or deleting in the middle shifts everything after the position (O(n)), which is where linked lists win on paper. In practice the cache-friendliness of contiguous memory often makes dynamic arrays faster anyway.
Operations
| Operation | Complexity |
|---|---|
| index / update | O(1) |
| append | O(1) amortised |
| insert / delete middle | O(n) |
| resize (rare) | O(n) |
Where it's used
The default sequence container in nearly every language — buffers, lists, stacks, and anywhere order plus fast indexing matters.