Dynamic Arrays

Big idea

A dynamic array (often called a vector) is an array that grows as you add to it. In C you build one yourself: a struct that tracks a heap block, how many items it holds, and how many it has room for.

From a loop to a reusable type

In free and realloc you grew a list inside main. That works once. To reuse it — several lists, in any program — wrap the three pieces of state in a struct and give it a few functions:

typedef struct {
    int *data;     // the heap block
    int len;       // how many items are in use
    int cap;       // how many items fit before we must grow
} IntVec;

• len is what the user sees: items 0 to len - 1.
• cap is how big the block really is. len <= cap, always.
• When len == cap and we push again, double cap with realloc.

Watch it grow

Things to notice:

• IntVec v = {0}; sets all three members to zero — an empty vector with data = NULL.
• realloc(NULL, n) behaves exactly like malloc(n), so the very first push needs no special case.
• vec_push takes a pointer to the vector, because it must change len, cap, and data.
• sizeof *grown is "the size of one item", so the code stays right if you change int to double.
• *v = (IntVec) {0}; is a compound literal: a temporary struct of zeros, copied in.

A full little vector

Push, get, set, pop — and reading input of unknown length:

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

typedef struct { int *data; int len; int cap; } IntVec;

int vec_push(IntVec *v, int value) {
    if (v->len == v->cap) {
        int new_cap = v->cap == 0 ? 4 : v->cap * 2;
        int *grown = realloc(v->data, new_cap * sizeof *grown);
        if (grown == NULL) return 0;
        v->data = grown;
        v->cap = new_cap;
    }
    v->data[v->len++] = value;
    return 1;
}

int vec_pop(IntVec *v) {
    return v->data[--v->len];     // caller must check len > 0
}

void vec_free(IntVec *v) {
    free(v->data);
    *v = (IntVec) {0};
}

int main(void) {
    IntVec v = {0};
    int x;
    while (scanf("%d", &x) == 1) {
        if (!vec_push(&v, x)) {
            vec_free(&v);
            return 1;
        }
    }
    printf("read %d values\n", v.len);
    printf("last: %d\n", vec_pop(&v));
    printf("now %d values, first is %d\n", v.len, v.data[0]);
    vec_free(&v);
    return 0;
}

input
3 1 4 1 5 9 2 6

output
read 8 values
last: 6
now 7 values, first is 3

Why doubling?

Growing by one each time means copying the whole array on every push — 10,000 pushes copy about 50 million items. Doubling means a copy only when the size passes 1, 2, 4, 8, 16, … — and the total copying stays under twice the final length. On average a push is constant time.

#include <stdio.h>

int main(void) {
    int cap = 1, len = 0, grows = 0;
    for (int i = 0; i < 100; i++) {
        if (len == cap) {
            cap *= 2;
            grows++;
        }
        len++;
    }
    printf("grows=%d cap=%d\n", grows, cap);
    return 0;
}

grows=7 cap=128

Starting from 1: 2, 4, 8, 16, 32, 64, 128 — seven grows for 100 items. A million items would need only 20.

Watch a pointer go stale

Common mistake

Keeping pointers into the vector across a push — see the question above. And forgetting to free: every vector needs exactly one vec_free when you're done.

Think of it like

A family that moves house only when they run out of bedrooms — and when they move, they buy one twice the size. Moves are rare, so most of the time a new arrival just takes a spare room. But after a move, the old address is no good.

Key terms

• Dynamic array / vector — An array that grows on demand.
• Length — How many items are in use.
• Capacity — How many items fit before the next grow.
• Amortised constant time — Cheap on average, even though an occasional step is expensive.
• Compound literal — (Type) { … }: a temporary value of a struct or array type.