A Structure That Points at Its Own Kind

The last lesson bought memory one block at a time; this one spends it on the data structure every C syllabus builds toward. A linked list is a chain of heap-allocated records, each holding one value and the address of the next record. Its whole apparatus is things you already own: struct from chapter 10, -> and NULL from chapter 11, malloc and free from last lesson. The only genuinely new idea fits in one declaration:

struct Node {
    int value;
    struct Node *next;
};

Read next carefully: it is a pointer to struct Node, not a struct Node. That distinction is what makes the type legal. A struct containing an actual member of its own type would have to contain itself, which contains itself, and so on — the compiler could never compute its size, and struct Node { int value; struct Node next; }; is rejected with field 'next' has incomplete type. A pointer is different: it is just an address, its size known before the struct is even finished, so a struct may hold a pointer to its own type, never an instance of it. That one legal pointer is the entire trick.

A three-node list holding 10, 20, 30 looks like this, with NULL in the last next marking the end:

head
  |
  v
+-------+----+     +-------+----+     +-------+------+
| 10    |  --+---> | 20    |  --+---> | 30    | NULL |
| value | next     | value | next     | value | next |
+-------+----+     +-------+----+     +-------+------+

Three Nodes by Hand

Before any loops, build that exact picture manually: allocate three nodes, wire the arrows, walk the chain.

It prints 10, 20, 30, one per line. Two details deserve a second look. The failure path frees all three pointers even though some may be NULL — that is deliberate, because free(NULL) is defined to do nothing, which makes clean-everything error handling safe. And the printing loop is the canonical list walk, worth memorizing as a unit: for (cur = head; cur != NULL; cur = cur->next). Start at the head, stop when the pointer runs off the end into NULL, advance by following the arrow. Every list operation for the rest of the course is a variation on this loop.

The Empty List and Insertion at the Head

Hand-wiring three named pointers does not scale; real lists grow one node at a time from a single pointer. The starting state is the most important convention in list code: an empty list is a head pointer holding NULL. Not a dummy node, not an uninitialized pointer — struct Node *head = NULL; is a complete, valid, walkable list of zero elements. The walk loop's condition fails immediately and prints nothing, which is exactly right.

The simplest correct way to grow it is insertion at the head. Aim the new node's next at the current front, then move head to the new node — in that order, because reversing the two assignments overwrites head before anyone has recorded where the old front was, orphaning the entire rest of the list:

node->next = head;
head = node;

Head insertion never needs a special case: when the list is empty, head is NULL, so the first node's next becomes NULL and it is correctly the last node too. The price is order: each new node lands in front of the previous ones, so a list built by head insertion holds its input reversed.

Growing a List from Input

Here is the full lifecycle — build from the sentinel-guarded input loop, walk, free — in one program:

Fed the input 1 2 3 0, it prints 3 -> 2 -> 1 -> NULL and then 3 nodes: three checked allocations, each spliced in at the head, the reversal on full display. Note where the malloc check's failure path goes — it frees every node built so far before returning, because a list half-built at the moment allocation fails is still your allocation to release.

Freeing the List: Save Next Before Free

The teardown loop at the bottom is subtler than it looks, and it is this lesson's sharpest rule. The tempting version is wrong:

/* WRONG: reads cur->next from a freed node */
free(cur);
cur = cur->next;

Once free(cur) runs, the node's bytes are no longer yours, and reading cur->next from it is use-after-free — undefined behaviour, which this platform's AddressSanitizer converts from "usually seems to work" into an immediate abort. The correct order is the one in the program: copy the successor into saved while the node is still alive, then free, then step:

saved = cur->next;
free(cur);
cur = saved;

One malloc per node going in, exactly one free per node coming out, and the escape route memorized before the bridge is burned.

Why Lists Exist When Arrays Already Do

An array is one contiguous block: instant a[i] indexing and cache-friendly scans, but its size is fixed at allocation, and growing means the realloc-and-copy dance from last lesson. A linked list grows one node per element with no capacity to guess and no copying, and head insertion costs the same two assignments whether the list holds zero nodes or a million. The bill: no indexing — reaching element i means walking i arrows — and nodes scattered across the heap, which modern caches dislike. For this course the list earns its place as the structure that grows without limits, and as the exam topic it has been for forty years.

Key Takeaways

  • struct Node { int value; struct Node *next; }; is legal because next is a pointer, whose size is known; a member of the struct's own type would make the size infinite 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 node->next = head; head = node; in that order, works on an empty list unchanged, and stores input in reverse.
  • The canonical walk is for (cur = head; cur != NULL; cur = cur->next), terminating at the NULL that ends every list.
  • Freeing must save cur->next before free(cur); reading a freed node is use-after-free, undefined behaviour, and an instant ASan abort here.
  • Versus arrays: per-element growth and two-assignment head insertion, at the price of no indexing and cache-unfriendly scattered nodes.