Visual walkthrough — Dynamic memory — malloc, calloc, realloc, free

Everything here assumes only that you have seen a pointer (a variable that holds an address) and the heap (a big pool of memory you rent at runtime). We build the rest.

Step 1 — What a pointer to heap bytes even is

WHAT. We rent a slab of bytes from the heap and hold its starting address in a pointer v.

int *v = malloc(cap * sizeof(*v));

Let us name every symbol right where it appears:

$\underset{\text{how many int slots}}{\underbrace{\text{cap}}}\times \underset{\text{bytes in ONE int}}{\underbrace{\text{sizeof(*v)}}}=\underset{\text{the number malloc wants}}{\underbrace{\text{total bytes to rent}}}$

• sizeof(*v) reads as "the size of the thing v points at" — one int, typically $4$ bytes (see sizeof operator).
• cap (capacity) is how many int-sized boxes we asked for.

WHY this form. malloc speaks only in bytes, but we think in elements. The multiplication is the translator between the two languages.

PICTURE. v is an arrow. It does not point at "the array" — it points at the first byte of a fenced-off strip of heap. The strip is cap boxes wide.

Step 2 — Why we need TWO counters, not one

WHAT. We keep len (used) and cap (rented) as separate variables.

$\text{len}\le \text{cap}\text{always true, invariant of the whole design}$

• len marches from $0$ upward as we push values.
• cap only changes when we re-rent.

WHY. If we tracked only one number we could not tell "the strip is full" apart from "the strip is half empty." The gap cap - len is exactly the free room left.

PICTURE. Two rulers under the same strip: a solid amber bar of length len (filled), a cyan outline of length cap (rented). The white gap between the bar's tip and the fence is the room we can still write into.

Step 3 — The "am I full?" test

WHAT. Before every push we check one condition:

if (len == cap) { /* grow */ }

$\underset{\text{boxes used}}{\underbrace{\text{len}}}=\underset{\text{boxes rented}}{\underbrace{\text{cap}}}⟺\text{no free room left}$

WHY the == and not >=? Because our invariant from Step 2 guarantees len can never jump past cap — it rises one step at a time. So the only way to be "full" is exact equality. (>= would also work and is safer if you ever break the invariant; == documents the invariant.)

PICTURE. The amber "used" bar has grown until its tip touches the fence. No white gap remains. That touching moment is the trigger.

Step 4 — Why double the capacity (the heart of the derivation)

WHAT. When full, we set:

cap *= 2;

${\text{cap}}_{\text{new}}=2\times {\text{cap}}_{\text{old}}$

WHY doubling and not "add one"? This is the whole point, so let us see the cost.

Every time we grow, realloc may have to copy all len existing integers to a new spot. Copying k items costs k units of work.

• Grow-by-1 strategy: we copy on every push. Total copies to reach $n$ items: $1+2+3+\cdots +n=\frac{n(n+1)}{2}\approx \frac{n^2}{2}⟹O(n^2)$ Each term is "the array we had to copy at that push." That parabola of work is brutal.

• Doubling strategy: we only copy at sizes $1,2,4,8,\dots$ Total copies: $1+2+4+\cdots +n=2n-1⟹O(n)$ A geometric series that sums to less than twice n. The work is a flat line.

The word for "expensive rarely, cheap usually, averaging out to cheap" is amortized $O(1)$ per push.

PICTURE. Two curves on the same axes: the grow-by-1 parabola climbing steeply versus the doubling line staying low. The gap between them is the reason we double.

Step 5 — What realloc physically does

WHAT. We ask for a bigger strip:

int *tmp = realloc(v, cap * sizeof(*v));

$\text{realloc}(\underset{\text{old start address}}{\underbrace{\text{v}}},\underset{\text{new size in bytes}}{\underbrace{\text{cap}\times \text{sizeof(*v)}}})\to \underset{\text{maybe-new address}}{\underbrace{\text{tmp}}}$

realloc has two possible moves, and it chooses for you:

1. Extend in place — if the boxes right after your strip happen to be free, it just moves the fence outward. tmp == v (same address).
2. Relocate — if the neighbours are occupied, it rents a fresh, bigger strip somewhere else, copies your len old integers into it, frees the old strip, and returns the new address. tmp != v.

WHY return into tmp and not v? Preview of Step 6 — because move (2) can fail, and if we overwrote v we would lose the address of the still-valid old strip. See Memory Leaks and Valgrind.

PICTURE. Two panels side by side. Left: the fence slides right, same address (cyan). Right: a whole new strip appears elsewhere, old bytes flow into it via an amber copy-arrow, and the old strip greys out (freed).

Step 6 — The degenerate case: realloc FAILS

WHAT. The heap can be exhausted. On failure realloc returns NULL and leaves the old block untouched and valid. That is why the safe pattern is:

int *tmp = realloc(v, cap * sizeof(*v));
if (!tmp) { free(v); return 1; }   // old block still ours → free it, bail out
v = tmp;                           // success → commit the new address

$\text{tmp}=\{\begin{array}{ll}\text{new valid address}& \text{success}\\ \text{NULL}& \text{failure, and }\text{v}\text{ still valid}\end{array}$

WHY the temporary is not optional. Trace the broken version v = realloc(v, ...):

• On failure realloc returns NULL.
• We just wrote that NULL into v.
• The old strip is still rented — but its only address is gone. Unreclaimable. That is a memory leak.

PICTURE. The broken path: realloc returns NULL, the arrow v is bent to point at nothing (NULL), and the old amber strip floats away untethered — leaked. Beside it, the correct path keeps v aimed at the old strip until tmp is proven good.

Step 7 — The write, and the zero-length edge

WHAT. With room guaranteed, we finally store the value and advance:

v[len++] = x;

$\underset{\text{box at index len}}{\underbrace{\text{v[len]}}}=x,\text{then}\underset{\text{used count}}{\underbrace{\text{len}}}+=1$

len++ is post-increment: use the old len as the index, then bump it. So we write into the first empty box, then mark it as used.

Edge cases you must never trip on:

• realloc(v, 0) — asking for zero bytes. The standard permits it to either free and return NULL, or return a tiny non-NULL "empty" block. Never rely on which — that is implementation-defined behaviour. Don't grow to $0$.
• realloc(NULL, n) — if the first argument is NULL, realloc behaves exactly like malloc(n). This is why some code starts with v = NULL and lets the first realloc do the first allocation.
• First push when cap starts at $0$ — then cap *= 2 stays $0$ (twice nothing is nothing!). That is why we seed cap = 2 (or special-case cap = cap ? cap*2 : 1). A pure "double" is helpless against a zero start.

PICTURE. The box at index len lights up amber as x drops in; a small arrow shows len stepping one box to the right afterward. Inset: the 0 * 2 = 0 trap crossed out in amber.

The one-picture summary

The entire life of a growable buffer: rent small → fill → detect full → double & (maybe) relocate → commit tmp into v → keep filling → free at the end. One arrow, one strip, doubling at the powers of two.

Active Recall