Lesson 4 · Linear structures

Static vs Dynamic Arrays

Every array is a contiguous block of memory. A static array fixes that block for its lifetime; a dynamic array adds a size and a capacity, and when it runs out it allocates a bigger block and copies. That single difference explains why appending is amortised O(1) rather than plain O(1).

Same Layout, Different Policy

Both kinds of array store elements in a single contiguous block with a fixed element width, so both get O(1) indexing from the same address arithmetic: base + i × width. The layout is identical. What differs is what happens when the block runs out.

A static array has its capacity fixed when it is created and it never changes. int arr[100] in C, or a Java array declared with new int[100], will hold exactly 100 elements for its entire life. Writing past the end is undefined behaviour in C and a checked exception in Java, but in neither case does the array grow.

A dynamic array presents an interface that appears unbounded — vector in C++, ArrayList in Java, list in Python, Vec in Rust — while still using a fixed block underneath. When the block fills, the structure quietly allocates a larger one and moves everything into it.

So a dynamic array is not a different data structure. It is a static array plus a growth policy, and understanding the policy is what explains its performance.

Two numbers must be tracked, and confusing them is a persistent source of bugs. The length (or size) is how many elements are actually stored. The capacity is how many the current block could hold. Capacity is always at least the length, and usually more — the difference is reserved space held for future appends.

Static arrays also come in two placements worth distinguishing. A stack-allocated array is created and destroyed automatically with its scope and is very fast, but is limited to a few megabytes. A heap-allocated one, via malloc or new, can be much larger and lives until explicitly freed — its size is still fixed at allocation, so it is static in the sense that matters here even though the size may be a runtime value.

Both use one contiguous block, so both index in O(1)
A static array's capacity never changes after creation
A dynamic array is a static array plus a growth policy
Length is what exists; capacity is what currently fits

What a Resize Actually Costs

When an append finds the block full, the array cannot simply extend in place. The memory immediately after the block belongs to something else — another allocation, or nothing mapped at all — so extending is not an option the allocator can offer.

Instead, three things happen. A new, larger block is allocated. Every existing element is copied into it. The old block is freed. The copy is O(n), and for non-trivial types in C++ it is n move or copy constructor calls rather than a flat memcpy.

Two consequences follow that catch people out.

Pointers and references are invalidated. Any pointer, reference, or iterator into the old block now points at freed memory. In C++ this is a well-known hazard: holding a reference to a vector element and then pushing onto that vector is undefined behaviour. Languages with garbage collection avoid the dangling pointer, but an index held across a resize still remains valid while a cached reference to the underlying storage may not.

Peak memory is roughly triple the data. During the copy, both the old block and the new one are allocated simultaneously. Growing a 1 GB array to 2 GB requires 3 GB available at the moment of the copy, which is how programs fail with out-of-memory errors while apparently using far less than the machine has.

Deletion is not symmetric. Removing elements lowers the length but typically leaves the capacity alone, so an array that was briefly large keeps holding that memory. C++ provides shrink_to_fit to request the release; Java's ArrayList has trimToSize. Automatic shrinking is generally avoided because it would cause thrashing when a length oscillates around the threshold.

A full block cannot extend — allocate, copy everything, free the old
Every existing pointer, reference and iterator becomes invalid
Both blocks exist during the copy, so peak memory is about 3× the data
Shrinking is not automatic; capacity persists after removals

Why Doubling Makes Append Amortised O(1)

If a resize is O(n), an append that triggers one is O(n) — so how is appending described as constant time? The answer is in how much the array grows, and the analysis is worth doing rather than accepting.

Suppose the array grew by a fixed amount, say 10 slots, each time. Then appending n elements triggers n/10 resizes, and the copying costs 10 + 20 + 30 + … + n, which sums to O(n²). Fixed-increment growth is genuinely quadratic and is the wrong policy.

Now suppose it doubles. Appending n elements triggers resizes at capacities 1, 2, 4, 8, … up to n, and the copying costs 1 + 2 + 4 + … + n. That geometric series sums to less than 2n — the total copying across all n appends is O(n), so the average per append is O(1).

The intuition behind the series: each resize costs twice as much as the previous one but happens half as often, and those two factors cancel exactly. Every element is copied on average at most twice over its lifetime, no matter how large the array becomes.

The growth factor need not be 2. C++'s std::vector typically uses 1.5 or 2 depending on the implementation; Java's ArrayList uses 1.5; Python's list uses a pattern close to 1.125 with a small additive term. Any factor strictly greater than 1 gives the amortised O(1) result — the sum remains geometric — so the choice is about the trade between wasted memory and resize frequency.

There is an argument that a factor below 2 allows freed blocks to be reused for later allocations, since the sum of all previous blocks eventually exceeds the next request. Factors of exactly 2 never permit this, which is one reason several implementations chose 1.5.

Growth policies and their total cost over n appends
Policy	Resizes	Total copying	Per append
Add a fixed amount	n / c	O(n²)	O(n)
Double	log₂ n	O(n)	Amortised O(1)
Multiply by 1.5	log₁.₅ n	O(n)	Amortised O(1)
Any factor > 1	O(log n)	O(n)	Amortised O(1)

Fixed-increment growth is O(n²) overall — the wrong policy
Doubling makes the copying a geometric series summing under 2n
Each element is copied at most twice on average over its lifetime
Any factor above 1 works; libraries use 1.5 or 2

Key reference

Terms, operations, and practical uses

Memory concepts

Contiguous MemoryA single, unbroken block of RAM where elements are stored immediately next to one another without gaps.
CapacityThe total number of elements a dynamic array's currently allocated memory block can hold.
Size (or Length)The number of elements currently occupied and valid within the dynamic array.

Performance metrics

Amortized O(1)While a single operation (like resizing) might be O(N), over a sequence of operations the average time per operation is O(1).
ReallocationThe O(N) process of requesting a new, larger memory block and copying all existing elements into it.
Cache LocalityThe performance benefit arrays enjoy because CPUs load sequential memory addresses into fast L1/L2 caches.

Growth strategies

Geometric GrowthMultiplying capacity by a factor (usually 1.5x or 2.0x) during reallocation to ensure amortized O(1) performance.
Arithmetic GrowthAdding a fixed amount to capacity (e.g., +100 elements). This is an anti-pattern as it leads to O(N^2) total insertion time.
ShrinkingSome implementations automatically halve their capacity when the size drops below 25% to recover wasted memory.

Implementation

Appending to a Dynamic Array

# STATIC: capacity fixed at creation, never grows, never copies
static = [None] * 4                  # 4 slots, allocated once
for i, value in enumerate([1, 2, 3, 4]):
    static[i] = value
# static[4] = 5                      # IndexError -- there is no fifth slot


# DYNAMIC: capacity doubles when full, so appends never run out
class DynamicArray:
    def __init__(self, capacity=2):
        self.capacity = capacity
        self.size = 0
        self.arr = [None] * self.capacity
        self.copies = 0              # count the elements moved by resizes

    def append(self, val):
        if self.size == self.capacity:
            # full: allocate bigger and copy
            self.capacity *= 2                # doubling is what makes this amortised O(1)
            new_arr = [None] * self.capacity
            for i in range(self.size):
                new_arr[i] = self.arr[i]
                self.copies += 1
            self.arr = new_arr
        self.arr[self.size] = val             # the O(1) fast path
        self.size += 1

    def to_list(self):
        return self.arr[:self.size]


arr = DynamicArray()
for value in (1, 2, 3, 4):
    arr.append(value)

print(f'static  contains {static}, capacity fixed at 4, 0 copies')
print(f'dynamic contains {arr.to_list()}, capacity grown 2 -> {arr.capacity}, {arr.copies} copies')

#include <iostream>
#include <vector>
using namespace std;
class DynamicArray {
    int* arr;
    int capacity, size_, copies;
    public:
    DynamicArray(int cap = 2) : capacity(cap), size_(0), copies(0) {
        arr = new int[capacity];
    }
    ~DynamicArray() {
        delete[] arr;
    }
    void append(int val) {
        if (size_ == capacity) {   // full: allocate bigger and copy
            capacity *= 2; // doubling keeps appends amortised O(1)
            int* next = new int[capacity];
            for(int i = 0; i < size_; i++) {
                next[i] = arr[i];
                copies++;
            }
            delete[] arr;
            arr = next;
        }
        arr[size_++] = val; // the O(1) fast path
    }
    int size() const {
        return size_;
    }
    int cap() const {
        return capacity;
    }
    int moved() const {
        return copies;
    }
    int operator[](int i) const {
        return arr[i];
    }
};
int main() {
    // STATIC: capacity fixed at creation, never grows, never copies
    int stat[4];
    for (int i = 0; i < 4; i++) stat[i] = i + 1;
    // stat[4] = 5;                       // out of bounds -- no fifth slot exists
    DynamicArray dyn;
    for (int v : {1, 2, 3, 4}) dyn.append(v);
    cout << "static  contains [";
    for(int i = 0; i < 4; i++) {
        if (i) cout << ", ";
        cout << stat[i];
    }
    cout << "], capacity fixed at 4, 0 copies\n";
    cout << "dynamic contains [";
    for(int i = 0; i < dyn.size(); i++) {
        if (i) cout << ", ";
        cout << dyn[i];
    }
    cout << "], capacity grown 2 -> " << dyn.cap() << ", " << dyn.moved() << " copies\n";
}

import java.util.Arrays;
public class Main {
    static class DynamicArray {
        private int[] arr;
        private int size = 0, copies = 0;
        DynamicArray(int capacity) {
            arr = new int[capacity];
        }
        void append(int val) {
            if (size == arr.length) {   // full: allocate bigger and copy
                int[] next = new int[arr.length * 2]; // doubling -> amortised O(1)
                for(int i = 0; i < size; i++) {
                    next[i] = arr[i];
                    copies++;
                }
                arr = next;
            }
            arr[size++] = val; // the O(1) fast path
        }
        int capacity() {
            return arr.length;
        }
        int copies() {
            return copies;
        }
        int[] values() {
            return Arrays.copyOf(arr, size);
        }
    }
    public static void main(String[] args) {
        // STATIC: capacity fixed at creation, never grows, never copies
        int[] stat = new int[4];
        for (int i = 0; i < 4; i++) stat[i] = i + 1;
        // stat[4] = 5;                        // ArrayIndexOutOfBoundsException
        DynamicArray dyn = new DynamicArray(2);
        for (int v : new int[]{1, 2, 3, 4}) dyn.append(v);
        System.out.println("static  contains " + Arrays.toString(stat)
        + ", capacity fixed at 4, 0 copies");
        System.out.println("dynamic contains " + Arrays.toString(dyn.values())
        + ", capacity grown 2 -> " + dyn.capacity() + ", " + dyn.copies() + " copies");
    }
}

Watch it run

Step through it

Running on Append 1, 2, 3, 4 — static array capacity 4 vs dynamic array starting at capacity 2

Output

Read all 10 Steps

Two arrays, two policies The static array reserves 4 slots up front and can never hold a fifth. The dynamic array starts at capacity 2 and buys more space when it runs out.
Append 1 size (0) < capacity (2), so the value is written straight into slot 0 and size becomes 1. This is the O(1) fast path.
Append 2 size (1) < capacity (2). Write slot 1, size becomes 2. The array is now full: size == capacity.
Append 3 hits the wall There is no slot 2, and the memory after the block may already belong to something else — so the array cannot simply extend in place.
Allocate double Request a fresh block of capacity 4. Doubling (not +1) is what makes the amortised cost constant.
Copy the old contents Every existing element is copied across. This is the O(N) cost of a resize, and the reason a single append can be slow.
Append 3 for real With room available the write is O(1) again. Free the old block; size is 3, capacity 4.
Append 4 size (3) < capacity (4). Straight write, no resize. Four appends cost 4 writes + 2 copies — amortised O(1) each.
What the static array did Same four values, zero copies, zero reallocation — because the size was known in advance. Its limit is absolute: a fifth append is a compile error or overflow, not a resize.
The trade Static: no overhead, no growth. Dynamic: one extra indirection and occasional O(N) copies, in exchange for never needing to know the size up front.

Amortised Is Not Guaranteed

The distinction matters in practice and is a standard exam point, so state it precisely: amortised O(1) means the average over a sequence of operations is constant, not that every individual operation is constant.

Most appends write one value and increment a counter — a few nanoseconds. Occasionally one allocates a block, copies a million elements, and frees the old block. The average is constant; the worst case for a single append remains O(n).

For most software this is irrelevant. For three situations it is not.

Real-time and latency-sensitive code. An audio callback with a deadline of a few hundred microseconds, a game's frame budget, or an interrupt handler cannot absorb an unpredictable pause. The standard mitigation is to reserve the expected capacity up front — vector::reserve, ArrayList(initialCapacity) — so no resize occurs during the critical section. If the maximum size is genuinely known, a static array removes the possibility entirely.

Code holding references into the array. Since a resize invalidates them, reserving capacity in advance also guarantees the addresses remain stable for the duration.

Memory-constrained environments. The transient tripling during a copy may not be available. Embedded systems frequently forbid dynamic allocation altogether for exactly this reason, alongside the fragmentation that repeated allocate-and-free introduces.

The choice between the two, stated simply: use a static array when the size is known and fixed, when allocation must be avoided, or when the environment demands predictability. Use a dynamic array everywhere else — which is most code, and why vector, ArrayList and list are the defaults in their languages.

One habit is worth forming regardless: when you know roughly how many elements are coming, say so up front. Reserving is a single call, eliminates every resize, and costs nothing when the estimate is close.

Amortised averages over a sequence — one append can still be O(n)
Reserve capacity when latency, stable references, or memory is tight
Peak memory during a copy can exceed what a constrained system has
Static when the size is known and fixed; dynamic for everything else