Arrays: The Foundation of Everything

Terminology

What & Why

Why Arrays Matter

An array is the simplest data structure in computer science: a contiguous block of memory storing elements of the same type at fixed-size intervals. Every element lives right next to its neighbor, so the CPU can jump to any element instantly using arithmetic.

The Four Key Properties

How It Works

Memory Layout and Indexing

When you allocate an array of $n$ elements of type $T$, the system reserves a contiguous block of $n \times \text{sizeof}(T)$ bytes. Each element's address is computed directly from the base address:

This is why indexing is $O(1)$: one multiplication and one addition, regardless of array size.

Insertion: The Shift Problem

Inserting at position $i$ requires shifting all elements from $i$ to $n-1$ one slot to the right. This is $O(n)$ in the worst case (inserting at position 0).

Dynamic Arrays: Growing on Demand

Static arrays have a fixed capacity, but most programs need arrays that grow. A dynamic array solves this by maintaining a backing buffer, a size counter, and a capacity. When size reaches capacity, it doubles the buffer.

Amortized Analysis: Why Doubling Works

Using the aggregate method: after $n$ pushes starting from capacity 1, the total copies from resizing is:

Total work for $n$ pushes is at most $n + 2n = 3n$, giving amortized cost $\frac{3n}{n} = O(1)$ per push.

Complexity Analysis

Space Overhead

A dynamic array with $n$ elements and doubling strategy uses at most $2n$ slots. Space utilization is always at least 50% after the first resize:

Implementation

FUNCTION DynamicArray():
    buffer ← allocate(1)
    size ← 0
    capacity ← 1

    FUNCTION push(element):
        IF size = capacity THEN
            new_buffer ← allocate(capacity × 2)
            COPY buffer[0..size-1] INTO new_buffer
            buffer ← new_buffer
            capacity ← capacity × 2
        buffer[size] ← element
        size ← size + 1

    FUNCTION get(index):
        IF index < 0 OR index ≥ size THEN ERROR
        RETURN buffer[index]

    FUNCTION insert(index, element):
        IF size = capacity THEN resize()
        FOR i FROM size DOWN TO index + 1:
            buffer[i] ← buffer[i - 1]
        buffer[index] ← element
        size ← size + 1

    FUNCTION delete(index):
        FOR i FROM index TO size - 2:
            buffer[i] ← buffer[i + 1]
        size ← size - 1

Real-World Applications

Key Takeaways