Array and Dynamic Array

Definition: A static array is a contiguous block of fixed-size memory storing elements of the same type; a dynamic array automatically resizes when capacity is exceeded.

How It Works

A static array is allocated as one contiguous block of memory large enough to hold a fixed number of same-sized elements. Because every element has the same size and they sit back to back, the address of any element can be computed directly:

Address(i) = Base_Address + i * Element_Size

This is what makes random access O(1): no traversal is needed, just arithmetic. The tradeoff is that the size is fixed at allocation time; growing a static array requires allocating an entirely new block and copying every element over.

A dynamic array wraps a static array with bookkeeping for length (elements in use) and capacity (total allocated slots), plus growth logic:

Appending when length < capacity just writes to the next free slot: O(1).
Appending when length == capacity triggers a resize: allocate a new block (typically 1.5x-2x the old capacity), copy all existing elements over, then write the new element. This single resize costs O(n).
Because resizes happen exponentially less often as the array grows (doubling means the next resize is twice as far away), the total copying work across n appends sums to a convergent geometric series, bounded by O(n) overall, not O(n^2). Spread across n appends, that’s amortized O(1) per append.

Growth factor is a real engineering tradeoff, not an implementation detail: Python lists grow by roughly 1.125x, Java’s ArrayList grows by 1.5x, and C++‘s std::vector commonly grows by 2x. A larger factor wastes more memory headroom (up to 50% unused after a resize with 2x growth) but triggers fewer, cheaper-per-element resizes; a smaller factor wastes less memory but resizes more often.

Shrinking is asymmetric with growing: most languages never automatically free unused capacity after elements are removed, on the assumption that a collection which grew large is likely to grow large again. Explicit calls like shrink_to_fit() (C++) or trimToSize() (Java) are required to actually release the extra memory.

Why Middle Insertion Is O(n)

Inserting at index i in an array of length n requires shifting every element from i to the end one slot to the right first, to make room:

insert(2, 'X') into [a, b, c, d, e]
step 1: shift c,d,e right by one -> [a, b, _, c, d, e]
step 2: write X into the gap     -> [a, b, X, c, d, e]

In the worst case (inserting at index 0), all n elements move, which is why repeatedly inserting at the front of an array-backed list is a classic accidental-quadratic pattern in loops.

Multi-Dimensional Arrays

A 2D array is conceptually a grid, but in memory it’s still one contiguous block, laid out either row-major (C, C++, Python’s NumPy by default) or column-major (Fortran, MATLAB). Row-major storage means Address(row, col) = Base + (row * num_cols + col) * Element_Size. This layout choice matters for performance: iterating in the storage order (rows first in row-major) walks memory sequentially and stays cache-friendly, while iterating against the grain jumps around memory and causes cache misses on nearly every access, even though both loops do the same asymptotic O(rows * cols) work.

Variants

Circular buffer (ring buffer): a fixed-capacity array where front and back indices wrap around modulo the capacity, giving O(1) enqueue/dequeue from both ends without ever shifting elements. See Stack and Queue for the full mechanism.
Sparse array: for data that’s mostly empty/default values (e.g. a huge but mostly-zero matrix), a hash map or list of (index, value) pairs stores only the non-default entries, trading O(1) access for large memory savings when density is low.
Bit array / bitset: packs boolean values one bit at a time instead of one byte or word, cutting memory by up to 8x-64x, common in bloom filters and flag sets where the value range is small and dense.

Complexity Analysis

Operation	Static Array	Dynamic Array
Access by index	O(1)	O(1)
Search (unsorted)	O(n)	O(n)
Insert/delete at end	N/A (fixed size)	Amortized O(1)
Insert/delete at start or middle	N/A	O(n) (element shifting)
Resize	N/A	O(n), amortized across appends
Space	O(n)	O(n), with up to ~50% slack after growth

Why It Matters

Serves as the underlying building block for most complex data structures (heaps, hash table buckets, stacks) because of cache locality and pointer-free access.
Contiguous memory layout makes sequential array access dramatically faster in practice than pointer-chasing structures, since it maximizes CPU cache-line reuse and enables hardware prefetching, effects that Big-O notation doesn’t capture but matter enormously in real workloads.
The amortized-O(1) append analysis is a foundational example of amortized complexity analysis, the same accounting technique used to reason about hash table resizing and many other structures.

Common Pitfalls

Inserting or deleting elements at arbitrary, non-tail positions requires O(n) element shifting, a common source of hidden quadratic behavior in loops that repeatedly call insert(0, x) or list.pop(0).
Unbounded resizing without a reserved capacity causes sudden memory spikes and repeated large copies when the final size is knowable in advance; calling reserve()/ensureCapacity() up front avoids this entirely.
Confusing length (elements in use) with capacity (allocated slots) leads to bugs when code assumes the two are always equal, e.g. iterating up to capacity and reading uninitialized slots.
Iterating over a dynamic array while appending to it can invalidate iterators or references, because a resize reallocates the entire backing buffer to a new memory address.
Assuming worst-case O(1) append instead of amortized O(1): a single unlucky append that triggers a resize really does cost O(n), which matters for latency-sensitive code (e.g. real-time systems) even if the average is fine.
Iterating a 2D array in the wrong order for the storage layout (column-first over a row-major array), silently turning a cache-friendly O(n) scan into one with far more cache misses despite identical asymptotic complexity.
Passing an array by value in languages that copy on assignment (e.g. Go slices’ underlying array semantics, or naive C array parameters) and being surprised that mutations don’t propagate as expected.

Comparison

	Static Array	Dynamic Array	Linked List	Hash Table
Random access	O(1)	O(1)	O(n)	O(1) avg (by key, not index)
Append at end	N/A	Amortized O(1)	O(1) with tail pointer	O(1) avg
Insert/delete in middle	N/A	O(n)	O(1) given node reference	N/A
Memory layout	Contiguous	Contiguous	Scattered, pointer-linked	Bucketed array
Resizing needed	No	Yes	No	Yes

Growth Factors Across Languages

Language / Type	Growth Factor	Notes
C++ `std::vector`	~2x	Implementation-defined; libstdc++ and MSVC both commonly use 2x
Java `ArrayList`	1.5x	`newCapacity = oldCapacity + (oldCapacity >> 1)`
Python `list`	~1.125x	Deliberately conservative to reduce over-allocation for small lists
Go `slice`	~2x below 1024 elements, ~1.25x above	Growth rate tapers off for very large slices to limit memory waste

A larger growth factor front-loads more wasted headroom in exchange for fewer, rarer resizes; the “right” factor is a genuine tuning tradeoff each language team makes differently.

Example

In Python, list.append(), and in C++, std::vector::push_back(), capacity roughly doubles once the array is full:

size=4, capacity=4  -> append(x) -> allocate capacity=8, copy 4 elements, size=5
size=8, capacity=8  -> append(x) -> allocate capacity=16, copy 8 elements, size=9

Appending 1 million items this way triggers only about 20 reallocations (log2 of 1,000,000 ≈ 19.9), not 1 million, which is exactly why amortized cost per append stays O(1) even though any individual append occasionally costs O(n). This is also why calling vector.reserve(1_000_000) up front before a known-size loop is a meaningful optimization in performance-sensitive C++ code: it eliminates all 20 of those reallocations entirely.

Amortized Analysis, Concretely

The accounting method makes the amortized O(1) claim rigorous: charge each append 3 “credits.” One pays for writing the new element. The other two are banked. When a resize happens and copies k elements, those k elements each already banked 2 credits from when they were appended, which is exactly enough to pay for their own copy. Since every element only ever needs to bank credits once, the total credits spent across n appends is O(n), giving O(1) amortized per operation, even though the underlying sequence of actual costs is 1, 1, 1, 4, 1, 1, 1, 1, 8, 1, ... (spiking at each resize).

Real-World Systems

Python’s list, Java’s ArrayList, C++‘s std::vector, and JavaScript’s Array (when kept as a dense, non-sparse array internally) are all dynamic arrays under the hood, each with its own growth-factor tuning.
NumPy arrays are static, fixed-size contiguous blocks by design, chosen specifically for predictable memory layout and vectorized (SIMD) operations that a resizable structure would complicate.
Database systems store table rows in fixed-size pages that behave like static arrays at the page level; PostgreSQL’s heap file organization and most B-tree leaf nodes rely on this same contiguous-block, direct-offset-access principle.

Common Interview Questions

Why is appending to a dynamic array amortized O(1) instead of always O(1)? — because occasional resizes cost O(n), but geometric growth spaces those resizes out so their total cost across n appends stays O(n), averaging to O(1) per append.
How would you implement a dynamic array from scratch using only a fixed-size array primitive? — track length and capacity separately, and on a full append, allocate a new fixed array at a larger capacity, copy every element over, then continue appending into the new block.
Why does reserve()/ensureCapacity() matter for performance if the array resizes automatically anyway? — it eliminates the repeated reallocate-and-copy cycles entirely when the final size is known ahead of time, converting a series of amortized O(1) appends with real (if rare) O(n) spikes into a run of guaranteed O(1) writes into pre-allocated space.

Referenced by

Dig deeper

Spot an error in this note?