Dynamic Arrays

A plain C array has a fixed size, decided at compile time (or at allocation time for a malloced block) — it cannot grow. A dynamic array is a small piece of bookkeeping built on top of malloc and realloc that behaves like an array you can keep appending to, growing its underlying storage automatically as needed. This is exactly the idea behind C++'s std::vector, Python's list, and similar "growable array" types in other languages — they are all, underneath, doing what this page builds by hand.

Two numbers: size and capacity

The key insight is tracking two separate numbers: size (how many elements are actually in use) and capacity (how many elements the current allocation can hold before it needs to grow). Appending is cheap as long as size < capacity; only when the array is full does it need to allocate a bigger block.

A worked example: a growable int array

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    int size;      // number of elements currently stored
    int capacity;  // number of elements the allocation can hold
} IntArray;

void int_array_init(IntArray *arr, int initial_capacity) {
    arr->data = malloc((size_t)initial_capacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initial_capacity;
}

void int_array_push(IntArray *arr, int value) {
    if (arr->size == arr->capacity) {
        // Full: double the capacity and reallocate.
        int new_capacity = arr->capacity * 2;
        int *new_data = realloc(arr->data, (size_t)new_capacity * sizeof(int));
        if (new_data == NULL) {
            fprintf(stderr, "out of memory\n");
            exit(1);
        }
        arr->data = new_data;
        arr->capacity = new_capacity;
    }

    arr->data[arr->size] = value;
    arr->size++;
}

void int_array_free(IntArray *arr) {
    free(arr->data);
    arr->data = NULL;
    arr->size = 0;
    arr->capacity = 0;
}

int main(void) {
    IntArray arr;
    int_array_init(&arr, 2);   // start small on purpose, to see it grow

    for (int i = 1; i <= 10; i++) {
        int_array_push(&arr, i * i);
        printf("size=%d capacity=%d\n", arr.size, arr.capacity);
    }

    printf("values: ");
    for (int i = 0; i < arr.size; i++) {
        printf("%d ", arr.data[i]);
    }
    printf("\n");

    int_array_free(&arr);
    return 0;
}

size=1 capacity=2
size=2 capacity=2
size=3 capacity=4
size=4 capacity=4
size=5 capacity=8
size=6 capacity=8
size=7 capacity=8
size=8 capacity=8
size=9 capacity=16
size=10 capacity=16
values: 1 4 9 16 25 36 49 64 81 100

realloc may move the block

`realloc` may return a different address than the one it was given — if there is not enough room to grow the block in place, it allocates a new, larger block, copies the old contents over, and frees the original. That is exactly why `int_array_push` always reassigns arr->data from `realloc`'s return value rather than assuming the address stays the same.

Why doubling, not adding a fixed amount

Growth strategy matters for performance

It might seem simpler to grow the capacity by a fixed amount (say, +10 elements) each time it fills up. The problem is that this makes appending `n` elements cost roughly `O(n^2)` total work, because every single growth step re-copies the entire array so far. Doubling the capacity instead means the total copying work across all the growth steps stays proportional to `n` — this is called amortized O(1) append, and it is why every practical dynamic array implementation (including `std::vector`) doubles (or otherwise grows geometrically) rather than adding a constant amount.

This hand-built IntArray is, in miniature, exactly what a std::vector<int> or a Python list of integers does internally: a contiguous buffer, a tracked size and capacity, and a doubling strategy for growth. Understanding it in C makes those higher-level structures far less mysterious.

Track size (elements in use) and capacity (elements allocated) separately.
Grow by reallocating to a larger block only when size reaches capacity.
Always reassign the pointer from realloc's return value — the block may have moved.
Doubling the capacity on growth keeps the amortized cost of appending O(1) per element.