dynamic array

An array that grows on demand by allocating a larger block and copying the existing items across when it runs out of room.

In more detail

Python's list is a dynamic array of pointers. Because each new block is a constant factor larger than the last, copies become rarer as the array grows and appends cost O(1) amortised. Inserting at the front is still O(n), since every item must shift one slot.

Example

The course's DynamicArray class counts each copy so you can see them become rare.

Related terms

Taught in

References