Dynamic Array
An array that doubles its capacity when full, so appends are amortized O(1).
Dynamic Array: Append five values
Full (2 of 2). Allocate 4 slots and copy the 2 existing values across.
Cost
- Access
- O(1)
- Append
- O(1) amortized
- Insert
- O(n)
- Delete
- O(n)
- Space
- O(n)
Append is O(n) on the resize step and O(1) otherwise. Amortized O(1).
Before this
Leads to
Topics that need this one first.