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
- array — A sequence of same-sized slots stored one after another in a single block of memory, so any slot can be reached by its index directly.
- capacity — The number of items a structure has room for before it must grow, as opposed to the number it currently holds.
- doubling strategy — Growing a full dynamic array by multiplying its capacity by a constant factor, typically two, rather than adding a fixed number of slots.
- amortised analysis — Measuring the average cost per operation over a long sequence of operations, so rare expensive steps are spread across many cheap ones.
- Python list — Python's built-in ordered, growable sequence, implemented as a dynamic array of pointers to objects.
Taught in
- Amortised Analysis: Why Append Is Cheap — Algorithms & Data Structures for Working Engineers
- Arrays: Contiguous Memory And Constant-Time Access — Algorithms & Data Structures for Working Engineers