CC Explainer
C · 4 · Dynamic Memory & Data Structures20 / 35 · 57%

Dynamic Arrays (Growable Vectors)

realloc with geometric growth gives amortized O(1) append.

Examples: realloc, capacity, amortized O(1)

shortcuts: ← prev · → next · M mark
1

The Struct

Track data, length and capacity separately.

Example
example
typedef struct {
    int   *data;
    size_t len;
    size_t cap;
} Vec;
2

Doubling Growth

Grow by a factor, never by one — that keeps append amortized O(1).

Example
example
int vec_push(Vec *v, int value) {
    if (v->len == v->cap) {
        size_t cap = v->cap ? v->cap * 2 : 4;
        int *tmp = realloc(v->data, cap * sizeof *tmp);
        if (!tmp) return -1;        // old block still valid
        v->data = tmp;
        v->cap  = cap;
    }
    v->data[v->len++] = value;
    return 0;
}
cap = 4, len = 4
slotvalue
010
120
230
340
→
cap = 8, len = 5
slotvalue
0-3copied
450
5-7free
realloc may move the block — every old pointer into it is invalidated.
3

The realloc Trap

Never assign realloc's result straight back to the original pointer.

Example
example
v->data = realloc(v->data, n);  // BUG: on failure the old block leaks

int *tmp = realloc(v->data, n);   // correct
if (!tmp) return -1;
v->data = tmp;
4

Cost

Where the time goes.

Complexity
push (no grow)O(1)
push (amortized)O(1)doubling
push (worst case)O(n)copy on realloc
indexO(1)
insert / remove middleO(n)