Lesson 5 · Linear structures

Static vs Dynamic Arrays

At the hardware level, all arrays are static blocks of contiguous memory. Dynamic arrays provide an abstraction on top of static arrays, automatically allocating a larger block and copying elements when the current capacity is reached.

Memory Allocation

When a static array is created, a contiguous block of memory is reserved. If you allocate space for 5 integers, you can never store a 6th integer in that same block.

A dynamic array keeps track of two properties: its current size (how many elements are in it) and its capacity (how much space is allocated). As long as size < capacity, adding an element is an O(1) operation.

Static arrays require knowing the max size upfront
Dynamic arrays track size and capacity
Languages like Java and Python use dynamic arrays by default

The Resizing Operation

When a dynamic array is full (size == capacity), it must grow. It cannot simply expand into adjacent memory because that space might be used by other variables.

Instead, it allocates a completely new, larger block of memory (usually double the capacity), copies all existing elements over, and then frees the old block.

Resizing requires allocating new memory
All elements must be copied (O(N) operation)
Old memory is garbage collected or freed

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.

Code example

Appending to a Dynamic Array

# STATIC: capacity is fixed at creation and can never grow
static = [None] * 4          # 4 slots, allocated once
for i, value in enumerate([1, 2, 3]):
    static[i] = value
# static[4] = 5              # would raise IndexError -- no room, ever

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

    def append(self, val):
        if self.size == self.capacity:   # full: allocate bigger and copy
            self.capacity *= 2
            new_arr = [None] * self.capacity
            for i in range(self.size):
                new_arr[i] = self.arr[i]
            self.arr = new_arr
        self.arr[self.size] = val
        self.size += 1

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

print('static  contains', static[:3], 'with fixed capacity 4')
print('dynamic contains', arr.arr[:arr.size], 'with grown capacity', arr.capacity)

#include <iostream>
using namespace std;

class DynamicArray {
public:
    int capacity = 2;
    int size = 0;
    int* arr = new int[capacity];

    void append(int val) {
        if (size == capacity) {
            capacity *= 2;
            int* new_arr = new int[capacity];
            for (int i = 0; i < size; i++) {
                new_arr[i] = arr[i];
            }
            delete[] arr;
            arr = new_arr;
        }
        arr[size] = val;
        size++;
    }
};

int main() {
    DynamicArray arr;
    arr.append(1);
    arr.append(2);
    arr.append(3);
    arr.append(4);
    return 0;
}

class DynamicArray {
    int capacity = 2;
    int size = 0;
    int[] arr = new int[capacity];

    public void append(int val) {
        if (size == capacity) {
            capacity *= 2;
            int[] new_arr = new int[capacity];
            for (int i = 0; i < size; i++) {
                new_arr[i] = arr[i];
            }
            arr = new_arr;
        }
        arr[size] = val;
        size++;
    }

    public static void main(String[] args) {
        DynamicArray arr = new DynamicArray();
        arr.append(1);
        arr.append(2);
        arr.append(3);
        arr.append(4);
    }
}

InputAppend 1, 2, 3, 4 to a dynamic array starting with capacity 2

Output

static  contains [1, 2, 3] with fixed capacity 4
dynamic contains [1, 2, 3, 4] with grown capacity 4

Example

Run the example step by step

Output

Amortized Complexity

Even though a resize operation takes O(N) time, it happens infrequently. If we double the capacity each time, the total cost of copying elements averages out to a constant cost per insertion.

This mathematical property is called amortized O(1) time complexity. For most practical purposes, appending to a dynamic array is considered extremely fast.

Resizes happen less often as the array grows
Total cost of N appends is O(N)
Average cost per append is O(1)

When to use Static vs Dynamic

If you know the exact maximum number of elements beforehand (e.g., sorting exactly 52 cards), use a static array. It skips the hidden overhead of tracking capacity and resizing.

If you are reading user input, streaming data, or building a list where the final count is unknown, a dynamic array is the correct choice.

Static: Predictable, zero overhead, memory efficient
Dynamic: Flexible, prevents buffer overflows, easy to use
Avoid repeated resizes by pre-allocating capacity if known