Arrays and Dynamic Arrays

An array stores fixed-size slots contiguously, allowing the address of position $i$ to be computed from a base address and stride:

$$\operatorname{address}(i)=\operatorname{base}+i\cdot\operatorname{stride}.$$

This gives constant-time indexed access and strong spatial locality.

Static versus dynamic

• A static array has fixed capacity.
• A dynamic array tracks both length and capacity. When full, it allocates a larger backing array and copies existing slots.

Geometric capacity growth makes end append amortized $O(1)$ even though an individual resize costs $O(n)$. This is an aggregate guarantee, not a promise that every append has constant latency.

Operation costs

Operation	Typical cost
Read/write by index	$O(1)$
Sequential traversal	$O(n)$
Append at end	amortized $O(1)$
Pop from end	$O(1)$
Insert/delete near front or middle	$O(n)$ shifts
Search unsorted values	$O(n)$

Binary search is $O(\log n)$ only when ordering is maintained and random access is available; maintaining that order can make updates expensive.

Language boundary

Low-level typed arrays usually store homogeneous values inline. A Python list is a dynamic array of object references: the reference slots are contiguous, while referenced objects may live elsewhere and may have different types.

Use boundary

Choose arrays for random access, compact iteration, sorting, matrices, and heap backing storage. Avoid front-of-array queue operations when frequent shifting would dominate.

Source

• Open Data Structures: Array-Based Lists