Dynamic Memory Allocation: short notes (Programming in C)

Revision mode

Introduction

Fixed-size automatic arrays have compile-time sizes, but a variable-length automatic array (VLA) can have a runtime size. Automatic objects have block-based lifetimes, not merely “until function return”; a VLA object lives from its declaration until execution leaves its scope. Allocated storage is needed when a block must outlive that scope or be explicitly resized at run time, for example for a linked-list node. C provides this through allocated storage: blocks requested from and returned to the heap with the functions in stdlib.h.

Every linked data structure in this subject is built this way. The price is that the programmer, not the language, is responsible for releasing each block exactly once and never touching it afterwards.

Conventions: C11, hosted, gcc with glibc on x86-64 Linux as the reference platform.

Prerequisites

Pointers: void *, pointer arithmetic, null pointers.
Scope, Storage Classes and Linkage: storage durations and the heap segment.

Core concepts

The four functions

Function	Effect	Returns
`void *malloc(size_t size)`	allocates `size` bytes, contents indeterminate	pointer to the block, or `NULL` on failure
`void *calloc(size_t n, size_t size)`	allocates `n * size` bytes, all bits zero	pointer, or `NULL`
`void realloc(void p, size_t size)`	for positive `size`, resizes and preserves contents up to the smaller size; may move	new block pointer, or `NULL` on failure with the old block retained; zero size needs a separate policy
`void free(void *p)`	releases the block; `free(NULL)` does nothing	nothing

Rules that follow from the standard:

Successful allocation is suitably aligned for object types with fundamental alignment. For an implementation-supported extended alignment, use aligned_alloc with its alignment and size-multiple preconditions. A void * result converts implicitly to object-pointer types in C; no cast is needed for int *a = malloc(...).
Always check for NULL before using the result.
realloc(NULL, size) behaves like malloc(size).
free(NULL) is harmless. A non-null pointer passed to free must identify a live allocation returned by a compatible standard allocator, including aligned_alloc, not an interior pointer. realloc likewise requires a compatible live allocation or NULL; do not use a stale pointer after successful resizing.
malloc(0) returns either NULL or a unique pointer that must not be dereferenced (implementation-defined which); either may be passed to free.
An allocated object lives from the allocation until it is freed, regardless of function calls and returns.

The `sizeof *p` idiom

The checked C11 functions below need <stdlib.h>, <stdint.h> and, for dup, <string.h>. Counts are size_t. Write the element size in terms of the pointer, reject zero or overflowing counts, and check every allocation before use:

int *make_int_array(size_t n) {
    int *a;
    if (n == 0 || n > SIZE_MAX / sizeof *a) return NULL;
    a = malloc(n * sizeof *a);
    if (a == NULL) return NULL;
    return a;                       /* caller owns n ints; initialize before reading */
}
struct node { int key; struct node *next; };
struct node *make_node(int key) {
    struct node *nd = malloc(sizeof *nd);
    if (nd == NULL) return NULL;
    nd->key = key;
    nd->next = NULL;
    return nd;
}

sizeof *a does not dereference a (the operand of sizeof is not evaluated), so it is valid even before a points anywhere.

Using `realloc` safely

int resize_ints(int **a, size_t new_count) {
    int *t;                         /* a is nonnull; *a is an owned live block or NULL */
    if (new_count == 0) { free(*a); *a = NULL; return 1; }
    if (new_count > SIZE_MAX / sizeof **a) return 0;
    t = realloc(*a, new_count * sizeof **a);
    if (t == NULL) return 0;         /* positive size: old allocation retained */
    *a = t;
    return 1;
}
int double_int_capacity(int **a, size_t *capacity) {
    size_t next;                    /* a and capacity point to caller variables */
    if (*capacity == 0) next = 1;
    else {
        if (*capacity > (SIZE_MAX / sizeof **a) / 2) return 0;
        next = 2 * *capacity;
    }
    if (!resize_ints(a, next)) return 0;
    *capacity = next;
    return 1;
}

Assigning the result straight to a (a = realloc(a, ...)) loses the only pointer to the old block if realloc fails, which leaks it. After a successful realloc the old pointer value must not be used, because the block may have moved.

Errors in managing the heap

Heap blocks: allocation, free, dangling pointer and leak — Figure 1. Four snapshots of the heap: p points to a new block; q copies p; after free(p) the block is released but q still points to it (dangling); and a block whose last pointer was overwritten is unreachable (leaked).

Error	What happens	Consequence
Memory leak	the last pointer to a block is lost or overwritten before `free`	memory stays allocated until the program ends; long-running programs grow
Dangling pointer	a pointer still refers to a block after `free`	any use is undefined behaviour
Double free	`free` called twice on the same block	undefined behaviour; often corrupts the allocator
Use of uninitialised memory	reading a `malloc` block before writing it	indeterminate values
Buffer overrun	writing past the end of the block	undefined behaviour; corrupts neighbouring blocks
Freeing non-heap memory	`free(&x)` for a local `x`, or `free(p + 1)`	undefined behaviour

Setting a pointer to NULL after free turns accidental reuse into a detectable null dereference and makes a second free harmless, but it does not fix other copies of the pointer.

AddressSanitizer and LeakSanitizer (gcc -fsanitize=address) detect these errors at run time. For a loop that allocates 100 bytes three times without freeing, LeakSanitizer reports "300 byte(s) leaked in 3 allocation(s)".

Returning heap memory from a function

Unlike a pointer to an automatic local object whose lifetime ends on block exit, a pointer to an allocated block remains valid after the allocating function returns, until that block is freed or a successful realloc ends its lifetime. Static-duration local objects also remain alive after return:

char *dup(const char *s) {                 /* like POSIX strdup */
    char *d = malloc(strlen(s) + 1);       /* +1 for the '\0' */
    if (d) strcpy(d, s);
    return d;                              /* caller must free(d) */
}

The function's documentation must say who frees the block.

How it works: dynamic two-dimensional arrays

Two common ways to get a rows-by-cols matrix at run time:

Array of row pointers (rows may live anywhere; each m[i] is a separate block): ``c int **make_matrix(size_t rows, size_t cols) { int **m; if (rows == 0 || cols == 0 || rows > SIZE_MAX / sizeof *m || cols > SIZE_MAX / sizeof **m) return NULL; m = malloc(rows * sizeof *m); if (m == NULL) return NULL; for (size_t i = 0; i < rows; ++i) { m[i] = malloc(cols * sizeof **m); if (m[i] == NULL) { while (i > 0) free(m[--i]); free(m); return NULL; } } return m; /* caller initializes cells, then frees each row and m */ } ``
One contiguous block with a pointer to array (requires cols known at compile time, or a VLA type): ``c typedef int Row4[4]; Row4 *make_rows4(size_t rows) { Row4 *g; if (rows == 0 || rows > SIZE_MAX / sizeof *g) return NULL; g = malloc(rows * sizeof *g); if (g == NULL) return NULL; return g; /* caller initializes cells; one free(g) */ } ``

In the first form m[i][j] follows two pointers; in the second it is a single address computation, as for a declared 2D array (Arrays and Their Relation to Pointers).

Growing an array: amortised analysis

A dynamic array (vector) stores size elements in a block of capacity elements. When an insertion finds size == capacity, it allocates a block of twice the capacity and copies the elements. Starting from capacity 1 and inserting $n$ elements, the copies happen when the size reaches $1, 2, 4, \ldots, 2^k$ , where $2^k < n$ , so the total number of element copies is

1 + 2 + 4 + \cdots + 2^k = 2^{k+1} - 1 < 2n .

Hence $n$ insertions cost $O(n)$ in total, an amortised $O(1)$ per insertion, even though a single insertion can cost $\Theta(n)$ . For $n = 1024$ the copies total 1023; for $n = 1025$ they total 2047. Growing by a constant amount instead (capacity $+c$ ) gives $\Theta(n^2/c)$ total copies.

Worked examples

All outputs below are for C11 with gcc and glibc on x86-64 Linux (LP64).

Example 1. With int *a = malloc(5 * sizeof *a) filled with a[i] = i * i, and int *c = calloc(5, sizeof *c): a[4] is 16, c[0] and c[4] are 0. After a successful realloc to 10 elements and a[i] = -i for $i = 5..9$ , the old values are kept: a[3] is 9, a[4] is 16, a[9] is $-9$ .

Example 2. dup("heap") returns a new block holding "heap", length 4, size 5.

Example 3. With the row-pointer matrix and m[i][j] = 10 * i + j for a $3 \times 4$ matrix, m[2][3] is 23 and m[1][0] is 10.

Important properties and observations

malloc returns indeterminate contents; calloc returns zeroed memory.
Check every allocation for NULL; use a temporary pointer with realloc.
Each block must be freed exactly once, with exactly the pointer that the allocator returned.
free(NULL) is safe; free does not change the pointer variable itself.
An allocated block can outlive its allocating function while the allocation remains live. An automatic local does not outlive its lifetime; a static-duration local remains alive after return.
Doubling growth gives amortised $O(1)$ insertion; constant-increment growth does not.
Repeated allocation and freeing of blocks of different sizes leads to fragmentation, the same problem studied for OS memory allocation.

GATE examination perspective

"Which statement causes a dangling pointer / memory leak?" Track every pointer to each block across free and reassignment.
malloc versus calloc initial contents.
Returning addresses: a pointer to a still-live allocated block may be returned. Returning &local leaves a dangling pointer if local is an automatic object whose lifetime ends on block exit; a static-duration local is not subject to that lifetime limit.
Amortised cost of a doubling array or of a sequence of realloc calls.
Size expressions: malloc(n * sizeof(int *)) allocates pointers, not ints; read the type carefully.

Summary

Sources

ISO/IEC 9899:2011 (C11), committee draft N1570, (consulted 2026-11-09): Section 6.2.4 (storage durations), 7.22.3 (memory management functions: general rules in the introductory paragraphs of 7.22.3, 7.22.3.2 calloc, 7.22.3.3 free, 7.22.3.4 malloc, 7.22.3.5 realloc).
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009: Section 17.4 (dynamic tables) for the amortised analysis of table doubling.
B. W. Kernighan and D. M. Ritchie, The C Programming Language, 2nd ed., Prentice Hall, 1988: Section 7.8 (miscellaneous functions, including storage allocation) and Section 8.7 (example: a storage allocator).