Arrays and Dynamic Arrays

Contiguous memory with O(1) indexing; dynamic arrays grow by reallocating.

Beginner

An array stores elements next to each other, so element $i$ is at base + i * size — instant access. Inserting or deleting in the middle shifts elements: $O(n)$ .

A dynamic array (Python list, C++ vector, Java ArrayList) doubles its capacity when full, so appending is $O(1)$ amortised.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)