Linked lists

Introduction

A linked list is a chain of nodes. Each node holds a value and a pointer to the next node; the last one points to NULL. Unlike an array, it can grow one node at a time, and inserting at the front is instant.

An array has to live in one continuous block, so growing it means copying. A linked list scatters its nodes through memory and joins them with pointers, which brings together everything you have learned about structs, pointers and the heap.

How it works

Building a list

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

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

int main(void) {
    struct node *head = NULL;
    for (int v = 1; v <= 3; v++) {
        struct node *n = malloc(sizeof(struct node));
        n->value = v * 10;
        n->next = head;
        head = n;
    }
    printf("first value: %d\n", head->value);
    return 0;
}

Watch the heap. Each malloc adds a new struct node box, and the arrows show the chain: head → first node → next node → ... → NULL. Inserting at the front takes two steps: point the new node at the old head, then move head to the new node.

Syntax

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

struct node *n = malloc(sizeof(struct node));
n->value = 5;
n->next = head;
head = n;

Example

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

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

struct node *push(struct node *head, int value) {
    struct node *n = malloc(sizeof(struct node));
    n->value = value;
    n->next = head;
    return n;
}

int main(void) {
    struct node *head = push(push(push(NULL, 3), 2), 1);
    int sum = 0;
    for (struct node *p = head; p != NULL; p = p->next) {
        sum += p->value;
    }
    printf("sum %d\n", sum);
    while (head != NULL) {
        struct node *next = head->next;
        free(head);
        head = next;
    }
    return 0;
}

for (struct node *p = head; p != NULL; p = p->next) visits every node: the arrow from p hops along the chain. To free a list, save next before freeing the current node, because after free you must not read it.

Line by line

1. struct node holds a value and a pointer to the next node.
2. push makes a new node, points it at the old head and returns it.
3. The nested calls build the list 1, 2, 3.
4. The for loop follows next from node to node, and adds up the values.
5. The while loop saves next before each free, and so releases every node.

Expected result

sum 6

In the real world

Operating systems keep lists of running processes, and memory allocators keep lists of free blocks. Hash tables use small linked lists to handle collisions, which you will meet in the Data Structures course.

Common mistakes

• Losing the head: if nothing points to the first node any more, the whole list leaks.
• Reading p->next after free(p).
• Forgetting to set the last node's next to NULL.

Best practices

• Draw the pointers before changing them.
• Check for NULL before following next.
• Write a function that frees the whole list.

Summary

A linked list is a chain of heap nodes, joined by next pointers and ending in NULL. Walking it means following pointers, and freeing it means saving next before each free.

Mark lesson complete