Dynamic Array — Amortized Resizing

Dynamic Array Operations

Growth Factor (on resize)

Live State

Size (n)

Capacity

Load factor

Resizes so far

Total pushes

Total copies

Avg. cost per push (amortized)

1.00 units

Event Log

Ready. Try Push ×10 to trigger a resize.

How it works

A dynamic array (Java ArrayList, C++ vector, Python list) is backed by a fixed-size block of memory of some capacity ≥ its size. Pushing when size < capacity just writes into the next slot — O(1). Pushing when the array is full triggers a resize: allocate a new block of capacity × growth slots and copy all size existing elements over — an O(n) operation.

if size == capacity:
    capacity = ceil(capacity * growth)   # e.g. ×2 or ×1.5
    new_block = allocate(capacity)
    for i in 0..size: new_block[i] = old_block[i]   # O(n) copy
    block = new_block
block[size] = value
size += 1

Why the amortized cost is still O(1): use the potential-method argument with Φ = 2·size − capacity (Φ ≥ 0 always, since capacity ≤ 2·size right after any resize with growth = 2). A cheap push (no resize) costs 1 and raises Φ by 2, for an amortized cost of 1 + 2 = 3. A resize-triggering push costs size + 1 (the copy plus the new write) but Φ drops from about size to about −size, a decrease of ≈2·size that cancels almost all of the copy cost. Averaged over any sequence of n pushes starting from empty, total real work is O(n), so the amortized cost per push is O(1) — this is exactly what "Total copies ÷ Total pushes" converges to below as you push more elements.

Push — appends one element; watch the size bar tick up and, when it hits capacity, a resize sweep copies every existing cell into a wider row.
Push ×10 — fires ten pushes back to back so you can see several resizes happen and watch the amortized-cost readout settle toward a small constant.
Pop — removes the last element (this simulator never shrinks capacity, mirroring most real implementations, which avoids thrashing between grow/shrink at the same boundary).
Growth factor — ×2.0 is the classic textbook choice; ×1.5 wastes less peak memory but needs slightly more resizes for the same n (a known real trade-off, e.g. .NET's List<T> historically used growth close to 2, some STL implementations use 1.5).

capacity = 4

Filled slot Empty capacity Just copied (resize)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.