AlgoScope

Dynamic Array

An array that doubles its capacity when full, so appends are amortized O(1).

Data structures, data structure, beginnerAlso called ArrayList, Vector, growable array
The array is full at 2 of 2. Capacity doubles to 4. 2 values are copied.308123
The array is full at 2 of 2. Capacity doubles to 4. 2 values are copied.308123

Dynamic Array: Append five values

Decision, step 4 of 9

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.