Dynamic Arrays

Fixed-size arrays have one big problem: you have to decide how many elements you need before you start. If you guess too small, you're stuck. Real programs almost never know the exact count ahead of time.

A dynamic array solves this. It wraps a regular fixed array with some extra logic that automatically grows the storage when it runs out of room. When the array fills up, it creates a bigger array behind the scenes, copies everything over, and keeps going. From the outside, it looks like an array with no size limit.

You already use dynamic arrays all the time — they're just called different things depending on the language: list in Python, ArrayList in Java, vector in C++, slice in Go.

In this lesson, you'll build one from scratch so you understand exactly what's happening under the hood.

Size vs. Capacity

A dynamic array keeps track of two separate numbers:

• size — how many elements are actually stored (the number you care about)
• capacity — how many elements the underlying array can hold (the reserved space)

Slots 5, 6, and 7 are allocated but empty. They're waiting for future appends.

The Resize Operation

When size == capacity and you try to append, the dynamic array has to grow:

function resize(dynArray, newCapacity):
    // Step 1: Create a new, bigger array
    newArray = allocate(newCapacity)
​
    // Step 2: Copy all existing elements into it
    for i = 0 to dynArray.size - 1:
        newArray[i] = dynArray.data[i]
​
    // Step 3: Swap in the new array and update capacity
    free(dynArray.data)
    dynArray.data = newArray
    dynArray.capacity = newCapacity

Step-by-step trace — appending 60 when the array is full:

Why Double? The Amortized O(1) Trick

Here's the thing: sometimes an append triggers a resize, which copies every element. That's slow! But most of the time, appending is instant. The question is: what's the average cost?

Watch what happens as we append 17 elements, starting with capacity 1:

Total copies across all 17 appends: 1 + 2 + 4 + 8 + 16 = 31. Plus 17 appends themselves. Grand total: 48 operations for 17 elements — that's less than 3 operations each on average.

The math works out to roughly 2n total operations for n appends. That means each append costs O(1) on average, even though the occasional resize costs O(n). This average-per-operation cost is called amortized O(1).

Why does doubling specifically achieve this? Because every time you copy n elements, you've just unlocked n new slots. By the time you need to copy again, you'll have done n more appends first. The expensive copies happen less and less often as the array grows.

Shrinking

If you delete many elements, the array wastes memory. A common approach: when size < capacity / 4, shrink the capacity down to capacity / 2.

Why capacity/4 instead of capacity/2? To avoid thrashing — a pattern where you resize up and down repeatedly:

// Bad: shrink at capacity/2
Array is full with 8 slots, size = 4 → shrink to 4
Append one element → resize back to 8
Delete one element → shrink to 4
Append one element → resize back to 8
...resizes forever!
​
// Good: shrink at capacity/4
This only triggers when you're using less than 25% of space.
You can add/remove several elements without thrashing.

Complete DynamicArray Implementation

class DynamicArray:
    data = allocate(1)     // start small
    size = 0
    capacity = 1
​
    function append(value):
        if size == capacity:
            resize(capacity * 2)   // double the capacity
        data[size] = value
        size = size + 1
​
    function get(index):
        if index < 0 or index >= size:
            error "Index out of bounds"
        return data[index]
​
    function set(index, value):
        if index < 0 or index >= size:
            error "Index out of bounds"
        data[index] = value
​
    function deleteAt(index):
        if index < 0 or index >= size:
            error "Index out of bounds"
        for i = index to size - 2:
            data[i] = data[i + 1]
        size = size - 1
        if size > 0 and size == capacity / 4:
            resize(capacity / 2)   // shrink to save memory
​
    function insertAt(index, value):
        if index < 0 or index > size:
            error "Index out of bounds"
        if size == capacity:
            resize(capacity * 2)
        for i = size - 1 down to index:
            data[i + 1] = data[i]
        data[index] = value
        size = size + 1
​
    function resize(newCapacity):
        newData = allocate(newCapacity)
        for i = 0 to size - 1:
            newData[i] = data[i]
        free(data)
        data = newData
        capacity = newCapacity
​
    function length():
        return size
​
    function isEmpty():
        return size == 0

Example 1: Append sequence — watch capacity double

Example 2: Delete with shrink