The Compiler Lets Go

Three lessons ago, every byte your programs used was sized before they ran. Now they ask the heap for exactly what the input demands, grow it when it runs out, and organize it into a structure that has no size limit at all. The chapter's machinery is four <stdlib.h> functions and one two-member struct; everything else is discipline — the NULL check, the assignment order, the one free per allocation that the compiler will never enforce for you but the sanitizer will. The recap, then one program that uses all of it.

Allocation and Ownership

malloc(n * sizeof(int)) sizes storage at run time, returns the block's address or NULL on failure, and every allocation is checked before use — a failed allocation is a return value, not an exception, and dereferencing the unchecked result is undefined behaviour. No cast on the result: malloc returns void *, which converts implicitly to any object pointer, and the historical (int *) cast used to silence the exact diagnostic that catches a missing <stdlib.h>. The block starts indeterminate; calloc(count, size) takes two arguments and zeroes it. Growing is realloc's job, and only through the temporary idiom: bigger = realloc(p, size); check, then p = bigger; — assigning straight to p overwrites the only pointer to the still-allocated old block when realloc fails, losing the data and leaking the memory in one line. The governing rule: every allocation has exactly one owner, the owner frees it exactly once on every path including early returns, free(NULL) is a defined no-op that makes clean-everything error paths safe, and use-after-free and double-free are undefined behaviour that ASan converts into immediate aborts. A leak has no line of its own, so LeakSanitizer reports the allocation site of the lost block.

Nodes and the Canonical Walk

struct Node { int value; struct Node *next; }; is legal because next is a pointer, whose size is known before the struct is finished; a member of the struct's own type would need infinite size and is rejected. The empty list is struct Node *head = NULL; — a complete, walkable list of zero elements, not a special case. Head insertion is two assignments in fixed order, node->next = head; head = node;, works unchanged on the empty list, and stores its input reversed, each new node landing in front of the last. Reading the list is the canonical walk, for (cur = head; cur != NULL; cur = cur->next), and destroying it is the walk with one extra rule: save cur->next before free(cur), because reading a pointer out of a freed node is use-after-free. One malloc per node in, exactly one free per node out.

Splice, Delete, and Who Updates head

Editing a list mid-chain needs the predecessor, the node before the action, because the pointer that must change lives inside it. The splice is node->next = pred->next; then pred->next = node; — in that order, because pred->next is momentarily the only pointer to the rest of the list, and reversing the assignments overwrites it before it is copied, leaving the new node pointing at itself and the tail leaked. Sorted insertion walks with pred->next != NULL && pred->next->value < value and collapses to head insertion when the list is empty or the value belongs first. Deletion is the splice run backward: unlink first, pred->next = doomed->next;, free second, never touch the node after. The head has no predecessor, so deleting it is head = head->next before freeing the old first node — and that is why list functions return the new head for the caller to assign back, head = deleteValue(head, target);, with the caller catching an inserting function's result in a temporary first, the realloc idiom again, so allocation failure leaves the old list reachable and freeable.

One Program, Whole Chapter

Five unsorted values arrive in order, each spliced into place by a checked allocation — 30 into the empty list, 12 and 5 in front of the head, 47 and 21 by the two-assignment splice — then 21 is unlinked and freed mid-chain, and the teardown loop saves each successor before burning the bridge behind it. Here it prints:

sorted:     5 -> 12 -> 21 -> 30 -> 47 -> NULL
deleted 21: 5 -> 12 -> 30 -> 47 -> NULL

Every path from all three lessons is in there: the temporary catching insertSorted's result before head moves, the head-deletion branch that returning the new head exists for, and one free for every malloc on the success path and the failure path alike. Trace each line back to its lesson, then take the quiz.

Looking Ahead

Chapter 14 steps outside the language proper into the preprocessor, the pass that rewrites your source before the compiler reads a token of it. #define macros bring convenience and their infamous parenthesization traps, #include finally gets explained rather than typed on faith, and conditional compilation with include guards shows how big programs keep hundreds of files from stepping on each other.