A dynamic array is an array that can grow as elements are added, removing the fixed-capacity limitation of a plain array while preserving its fast indexing. It appears in nearly every modern language under a different name: the C++ vector, the Java ArrayList, the Python list, and the Go slice are all dynamic arrays. Internally each holds an ordinary contiguous array plus a record of how many slots are in use and how many are allocated.
The mechanism for growth is reallocation. When an append would exceed the allocated capacity, the structure requests a new, larger block of memory, copies the existing elements into it, and frees the old block. Because copying every element is expensive, implementations do not grow by one slot at a time; they grow by a multiplicative factor, commonly doubling the capacity. Growing geometrically means the costly copies happen rarely enough that, spread across all the cheap appends in between, the average cost of an append stays constant. This averaged-out guarantee is called amortized O(1) time, and it is the central reason dynamic arrays are practical.
Because the underlying storage is still a contiguous array, indexing remains O(1): the element at position i is found by the same address arithmetic used in a fixed array. The dynamic array therefore keeps the access strength of an array and pays for its flexibility only in occasional reallocation cost and in some unused, reserved capacity. This is a space-time trade-off, holding spare room so that most appends need no copying.
The reasoning behind why the doubling strategy yields constant amortized cost is the kind of accounting that the foundational analysis of algorithms makes precise. Donald Knuth’s Volume 1, “Fundamental Algorithms,” establishes the methods for measuring how the work of such operations grows, the same analytical groundwork on which amortized analysis of resizable structures rests (Knuth’s pages at Stanford, verified 2026-06-08).