| Idea: |
- an array with a fixed capacity can hold new elements in constant time, but only until it fills up
- when the array is full, allocate a new array of twice the capacity and copy all elements over
- a single insert can thus take \(\Theta(n)\) time, but the expensive reallocations are rare: to reach one, we must first fill the free half of the array with cheap inserts, so \(n\) operations take \(O(n)\) time in total
- when only a quarter of the array is used, halve the capacity
|
| Advantages: |
- constant-time access to any element by index, and amortized constant-time insertion and deletion at the end
- elements are stored contiguously, which real hardware rewards (cache friendliness)
|
| Disadvantages: |
- a single insert can occasionally be slow — unsuitable where worst-case bounds matter (real-time systems)
- inserting or deleting in the middle still takes \(\Theta(n)\) time
- up to three quarters of the allocated memory may be unused
|
| Implementation: |
std::vector in C++, Vec in Rust, ArrayList in Java, list in Python- note: many implementations never shrink at all — leaving unused memory allocated buys freedom from reallocation churn
|