Linked Lists

Arrays are great when you know the size up front and want fast random access. They are awkward when you need to insert or remove items in the middle, or when you don't know how large the collection will grow.

The linked list is the canonical alternative. It's also the canonical "you actually understand pointers now" exercise. Each element of the list is a node on the heap, and each node holds a pointer to the next node.

The shape of a node

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

A few details worth unpacking:

• The struct is named struct Node and typedef'd to Node. The struct tag (struct Node) is needed inside the struct itself, because at that point the typedef name doesn't exist yet.
• The next field is a pointer to the same kind of struct. A pointer is the same size regardless of what it points at, so the compiler is happy.
• A next value of NULL means "no more nodes" — the end of the list.

head is just a pointer; it's not a node itself. An empty list has head == NULL.

Building a list, one node at a time

The traversal loop is the heart of working with linked structures:

for (Node *cur = head; cur != NULL; cur = cur->next) {
    // do something with cur->value
}

You always start at head, and you always stop when cur becomes NULL. This idiom appears in trees, graphs, and every list-like structure you'll write.

Prepending and appending

Prepending (adding to the front) is O(1). You just point the new node at the old head, then move the head:

Node *prepend(Node *head, int value) {
    Node *n = node_new(value);
    if (n == NULL) return head;
    n->next = head;
    return n;
}

Appending (adding to the back) is O(n) unless you also keep a tail pointer:

Node *append(Node *head, int value) {
    Node *n = node_new(value);
    if (n == NULL) return head;
    if (head == NULL) return n;
    Node *cur = head;
    while (cur->next != NULL) cur = cur->next;
    cur->next = n;
    return head;
}

Notice both functions return the (possibly new) head. The caller reassigns:

head = prepend(head, 5);
head = append(head, 99);

This pattern — "modify a structure, return the new root" — is one way to keep the call site simple. The alternative is passing a Node ** (a pointer to the head pointer). Both are correct; returning the new head is friendlier to read in beginner code.

Trace: building [10, 20, 30] by prepending

start:        head = NULL
prepend(30):  head -> [30 | NULL]
prepend(20):  head -> [20 | *] -> [30 | NULL]
prepend(10):  head -> [10 | *] -> [20 | *] -> [30 | NULL]

Prepending three values gives you the list in reverse of insertion order. If you want them in insertion order with O(1) inserts, keep a tail pointer too — that's how a queue is built.

Freeing a list

Every node was malloc'd. Every node must be free'd. The canonical loop:

void list_free(Node *head) {
    Node *cur = head;
    while (cur != NULL) {
        Node *next = cur->next;   // grab next BEFORE we free cur
        free(cur);
        cur = next;
    }
}

The temptation is to write cur = cur->next after free(cur). But that reads memory that has just been freed — undefined behavior. Always remember "save then free".

Inserting in the middle

To insert a new node after an existing one called prev:

Node *n = node_new(value);
n->next = prev->next;
prev->next = n;

Two pointer assignments. No shuffling of array elements. That O(1) insertion is exactly what people choose linked lists for.

To remove the node after prev:

Node *dead = prev->next;
prev->next = dead->next;
free(dead);

Why linked lists are a pointer workout

There's no way to misunderstand a pointer and still get a working linked list. To build one, you must keep two pictures simultaneously clear in your head:

1. Where the boxes live in memory (each node was malloc'd).
2. Which boxes point at which (the next arrows).

If those two pictures aren't crystal clear, the program crashes or leaks. If they are, every operation is just rearranging arrows. Once you can write list_free from scratch without looking it up, you have internalized pointers.

Multi-file challenge: a complete linked-list module

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

Node *list_prepend(Node *head, int value);
void  list_print(const Node *head);   // prints values space-separated, then '\n'
void  list_free(Node *head);

1 2 3

for (Node *cur = head; cur != NULL; cur = cur->next) {
  free(cur);
}