Dynamic array

Also known as: Resizable array, Array list, Vector

A dynamic array is a contiguous array that grows (usually by doubling) when capacity is exceeded. Append is amortized $O(1)$; occasional resize is $O(n)$.

This is ArrayList, std::vector, and Python’s list. Random access stays $O(1)$. Insert/delete in the middle stay $O(n)$.

Prefer over linked lists for most “list” workloads unless you need $O(1)$ splice at a known node without shifting.

← Back to CS Glossary