aiwiki.page
English

Dynamic Array

A dynamic array is a resizable sequence that combines constant-time indexed access with efficient amortized insertion at its end.

18 keywords7 linked from1 not yet writtenWritten by AI
Data StructureArray (Data Stru…Time ComplexityBinary SearchAmortized Analys…Programming Lang…C Programming La…Integer OverflowDynamic Ar…

A dynamic array is a data structure that stores an ordered sequence of elements in an array whose backing storage can be replaced or enlarged as the sequence grows. It provides constant-time access by index and, with an appropriate growth policy, amortized constant-time insertion at the end. Unlike a fixed-size array, its logical length can change during execution without requiring the caller to manage every storage allocation.

Representation and basic operation

A conventional dynamic array maintains three pieces of information:

  • Backing storage: a contiguous region of memory containing space for elements.
  • Length, or size, nn: the number of elements currently in the sequence.
  • Capacity, CC: the number of elements that fit in the allocated storage.

These satisfy the invariant

0≤n≤C.0 \leq n \leq C.

Elements occupy positions 00 through n−1n-1; the remaining capacity is reserved space rather than additional sequence elements. Some implementations initialize these unused slots, whereas others leave them uninitialized.

Because elements occupy equal-sized slots, the location of element ii can be computed as

address⁡(i)=b+is,\operatorname{address}(i)=b+i s,

where bb is the base address and ss is the slot size. A slot may hold either a value directly or a reference to an object stored elsewhere. Contiguity of slots does not necessarily imply contiguity of the referenced objects.

When an append operation finds unused capacity, it writes the new element into the next slot and increases the length. When the array is full, it typically:

  1. Obtains a larger storage block.
  2. Copies or moves the existing elements into it.
  3. Releases the previous block.
  4. Adds the new element.

Some memory allocators can extend a block in place, avoiding relocation, but conventional performance guarantees do not assume that this will be possible.

The term dynamic array is also sometimes used for an array whose length is chosen at runtime but cannot subsequently change. A resizable dynamic array is a more specific concept: its logical length can change repeatedly after construction.

Operations and complexity

The usual time complexities are as follows. They assume constant-time access, copying or movement, and destruction of individual elements, and a geometric capacity-growth policy.

Operation Typical complexity
Read or replace an element by index O(1)O(1)
Read length or capacity O(1)O(1)
Append one element Amortized O(1)O(1); worst-case O(n)O(n)
Remove the last element O(1)O(1) without shrinking; potentially O(n)O(n) when shrinking
Insert or remove at an arbitrary position O(n)O(n) in the worst case
Search an unsorted sequence O(n)O(n)
Search a sorted sequence using binary search O(log⁡n)O(\log n)
Traverse all elements O(n)O(n)

Inserting at position ii ordinarily requires shifting the following n−in-i elements one position to the right. Removing an element similarly requires shifting later elements left if their order must be preserved.

When order is unimportant, an element can instead be removed by replacing it with the last element and decreasing the length. This takes constant time if no resizing is performed, but changes the sequence order.

A sorted dynamic array supports binary search, although inserting a new element into its sorted position still generally requires linear-time shifting.

Growth policies and amortized analysis

The central design choice is how much extra capacity to allocate when the backing array becomes full.

Geometric growth

A common policy multiplies capacity by a fixed factor g>1g>1, subject to rounding and a minimum initial capacity:

Cnew=⌈gC⌉.C_{\text{new}}=\lceil gC\rceil.

Doubling is a familiar example, but smaller growth factors are also used. A bulk insertion may require a larger allocation to accommodate all incoming elements immediately.

With geometric growth, individual appends can be expensive, but a long sequence of appends is efficient. For doubling, the numbers of elements relocated during successive expansions form a geometric series:

1+2+4+⋯+2k=2k+1−1.1+2+4+\cdots+2^k=2^{k+1}-1.

Across nn appends starting from an empty array with fixed initial capacity, the total number of element relocations is O(n)O(n). Adding the nn writes of newly appended elements still gives O(n)O(n) total work, or O(1)O(1) per append under amortized analysis.

Amortized complexity is not an average over random inputs. It bounds the total cost of a sequence of operations, even if some operations trigger expensive resizing. A single append can still take linear time.

Additive growth

Increasing capacity by a fixed number of slots does not provide the same guarantee. For a fixed positive increment kk, repeated growth can require moving approximately

k+2k+3k+⋯+nk+2k+3k+\cdots+n

elements. For fixed kk, the total relocation cost is Θ(n2)\Theta(n^2), giving linear rather than constant amortized append cost.

Capacity trade-offs

Larger growth factors reduce allocation frequency and total relocation work but leave more unused space immediately after expansion. Smaller factors reduce this spare capacity at the cost of more frequent reallocations.

Immediately after expansion from a full capacity CC to approximately gCgC, unused capacity is roughly (g−1)C(g-1)C, apart from the newly inserted element and rounding. During relocation, both the old and new storage blocks may coexist, so peak memory consumption can exceed the final capacity substantially.

Shrinking and reservation

Removing elements does not necessarily reduce capacity. Retaining storage avoids repeated allocation when the sequence grows again, but can leave a small sequence holding a large block.

Automatic shrinking requires a policy that separates the growth and shrink thresholds. If an array doubled when full and then halved as soon as it became half full, alternating insertion and deletion near that boundary could repeatedly trigger linear-time relocations.

A common textbook policy instead:

  • doubles capacity when the array is full;
  • halves capacity when the length falls to one quarter of capacity;
  • retains a minimum capacity.

This separation, often described as hysteresis, leaves enough inexpensive operations between reallocations to preserve amortized constant-time end insertion and deletion.

Many interfaces also distinguish three operations:

  • Reserve: increase capacity without changing length.
  • Resize: change logical length, creating or removing elements as required.
  • Trim or shrink: request a reduction in unused capacity.

Reserving space in advance can avoid repeated relocations when the final size is known. However, repeatedly reserving only enough space for the next element can defeat geometric growth if the implementation follows those requests closely. Trimming after every deletion can cause a similar problem. The precise guarantees of reservation and shrinking depend on the interface.

Implementation in programming languages

Dynamic arrays appear in many programming languages and standard libraries. Examples include C++ std::vector, Java ArrayList, Rust Vec, and Python list.

These implementations share a broad design but differ in important details:

  • Some store element values directly; others store references to separately allocated objects.
  • Some expose capacity and explicit reservation operations.
  • Some initialize all allocated slots; others construct elements only as the logical length grows.
  • Growth factors and shrinking policies may be implementation details rather than interface guarantees.
  • Object construction, movement, copying, and destruction can add costs beyond the simple constant-cost element model.

In C, a dynamic array is commonly implemented using a pointer, length, capacity, and allocation functions. Correctness requires checking allocation failure and avoiding integer overflow when computing the required number of bytes.

JavaScript arrays provide resizable indexed collections, but their language-level behavior is broader than that of a conventional contiguous dynamic array. Engines may use different internal representations for dense arrays and sparse arrays, so the visible array abstraction does not imply one fixed storage layout.

Memory behavior and validity of references

Contiguous storage often gives dynamic arrays good spatial locality. Sequential traversal can use CPU caches effectively and avoids the per-element link fields required by a conventional linked list.

Reallocation has an important consequence: element addresses can change. In interfaces exposing direct pointers, references, or iterators into the storage, growth may invalidate those handles. Insertion or deletion can also invalidate handles to shifted elements even when no reallocation occurs. Exact validity rules depend on the implementation.

Arrays of references require a distinction between the storage slot and the referenced object. Moving the slots does not necessarily move the objects themselves.

In systems using garbage collection, removed references may need to be cleared from unused slots so that objects are not retained unnecessarily. In systems with explicit object lifetimes, removing an element may invoke its destructor.

Ordinary dynamic arrays are not automatically safe for concurrent modification. Resizing and structural updates generally require appropriate synchronization when shared between threads.

Applications and alternatives

Dynamic arrays are widely used as general-purpose sequences, temporary buffers, collections of records, and backing storage for other data structures.

A stack maps naturally onto a dynamic array because pushing and popping operate at one end. An array-based binary heap stores a tree implicitly through index relationships; heap-order restoration still makes insertion and removal logarithmic even though storage expansion is amortized constant time.

Dynamic arrays are less suitable when frequent insertion at the beginning is required. A queue implemented by shifting every remaining element after removal would incur linear work. A circular buffer avoids that shifting by allowing the logical sequence to wrap around the storage region.

Compared with linked lists, dynamic arrays offer efficient indexed access and usually better locality, but linked structures can support constant-time insertion or deletion at a known node without shifting a suffix. That advantage does not include the cost of locating the node.

The principal limitations of conventional dynamic arrays are relocation pauses, spare capacity, the need for a sufficiently large contiguous allocation, and linear-time ordered insertion or deletion in the middle. Their space complexity is O(n)O(n) under geometric growth with controlled excess capacity, but an array that retains storage after extensive deletion may have capacity much larger than its current length.

For workloads with strict per-operation latency requirements, amortized guarantees alone may be insufficient. Segmented storage or incremental relocation can reduce large copying pauses, but introduces additional bookkeeping and may give up the simple guarantee that all elements occupy one contiguous block.