Linked Lists

Big idea

A linked list is a chain of small heap blocks called nodes. Each node holds a value and a pointer to the next node; the last one points to NULL. It pulls together everything so far: structs, pointers, malloc, free, and loops.

The node

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

A struct that points to its own type. (Inside the braces the typedef name Node doesn't exist yet, so the member is written struct Node *next.)

The whole list is just a pointer to the first node, the head. An empty list is Node *head = NULL;.

Unlike an array, the nodes are not side by side in memory — each was malloc'd on its own and could be anywhere. The next pointers are the only thing holding the chain together.

Building a list: push to the front

Adding at the front is the simplest operation — make a node, point it at the old head, and make it the new head:

Why Node **head? push_front must change main's head variable. To change a variable, a function needs its address — and head is already a pointer, so its address is a pointer to a pointer. It's call by reference again, one level up (see Pointer to Pointer).

Walking the list

Nearly every list function is this loop:

for (Node *p = head; p != NULL; p = p->next) {
    /* use p->value */
}

Start at the head, stop at NULL, step with p = p->next.

Adding at the end, removing, freeing

#include <stdio.h>
#include <stdlib.h>

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

int push_back(Node **head, int value) {
    Node *n = malloc(sizeof *n);
    if (n == NULL) return 0;
    n->value = value;
    n->next = NULL;
    if (*head == NULL) {           // empty list: the new node IS the list
        *head = n;
        return 1;
    }
    Node *p = *head;
    while (p->next != NULL) p = p->next;   // find the last node
    p->next = n;
    return 1;
}

/* Removes the first node holding value. Returns 1 if one was removed. */
int remove_value(Node **head, int value) {
    Node *prev = NULL, *p = *head;
    while (p != NULL && p->value != value) {
        prev = p;
        p = p->next;
    }
    if (p == NULL) return 0;       // not found
    if (prev == NULL) *head = p->next;   // removing the head
    else prev->next = p->next;           // unlink from the middle or end
    free(p);
    return 1;
}

void print_list(const Node *p) {
    for (; p != NULL; p = p->next) printf("%d ", p->value);
    printf("\n");
}

void free_list(Node *p) {
    while (p != NULL) {
        Node *next = p->next;      // save it BEFORE freeing p
        free(p);
        p = next;
    }
}

int main(void) {
    Node *head = NULL;
    for (int i = 1; i <= 5; i++) push_back(&head, i * 10);
    print_list(head);
    remove_value(&head, 10);       // the head
    remove_value(&head, 30);       // the middle
    remove_value(&head, 50);       // the end
    print_list(head);
    free_list(head);
    return 0;
}

output
10 20 30 40 50 
20 40 

To remove a node, make the one before it skip over it (prev->next = p->next), then free it. Removing the head is the special case: there's no node before it, so head itself moves.

Watch a node being removed

Freeing: the order matters

#include <stdio.h>
#include <stdlib.h>

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

int free_list(Node *p) {
    int freed = 0;
    while (p != NULL) {
        free(p);
        freed++;
        p = NULL;   // can't read p->next after free(p), so stop here
    }
    return freed;
}

int main(void) {
    Node *head = NULL;
    for (int i = 0; i < 3; i++) {
        Node *n = malloc(sizeof *n);
        n->value = i;
        n->next = head;
        head = n;
    }
    printf("freed %d nodes\n", free_list(head));
    return 0;
}

output
freed 3 nodes

The obvious loop body — free(p); p = p->next; — reads p->next from memory that was just freed: a use-after-free that may even seem to work. This version avoids it by stopping after one node, which leaks the other two. Fix it properly: save p->next in a variable before free(p), as free_list in the full example does.

Arrays vs linked lists

In practice vectors win most of the time. Lists shine when you insert and remove in the middle a lot — and they're the foundation for stacks, queues, hash tables, and trees.

Common mistakes

• Losing the head. Walking with head = head->next in main loses the start of the list — and leaks every node you've passed. Walk with a separate pointer.
• Forgetting the empty list. Every function should work when head is NULL.
• Leaking. Every malloc'd node needs a free: call free_list when you're done.

Think of it like

A treasure hunt. Each clue (node) holds a prize (value) and says where the next clue is hidden (next). You can't jump to clue five — you follow the trail from the first. But slipping a new clue into the middle only means rewriting one note.

Key terms

• Node — One element: a value plus a next pointer.
• Head — A pointer to the first node; NULL for an empty list.
• Traversal — Visiting each node by following next until NULL.
• Self-referential struct — A struct with a pointer to its own type.
• Unlink — Make the previous node skip one, removing it from the chain.