Questions
10 of 19
What is a Dynamic Array (ArrayList/Vector)? How does it grow?
Difficulty: 2/10
Dynamic Arrays
A dynamic array is an array-backed data structure that automatically increases its capacity when the existing storage becomes full. Examples include Java ArrayList and Vector. Internally, the implementation allocates a larger array and copies the existing elements into it.
javascript
- 1
Capacity is different from the current logical size.
- 2
When capacity is exhausted, a larger backing array is allocated.
- 3
Existing elements are copied into the new array.
- 4
The growth factor is implementation-dependent.
- 5
The resize operation itself is O(n), but ordinary append is amortized O(1).
Follow-up Questions
- Why is append amortized O(1)?
- What is the difference between size and capacity?