Data structures in C · about 60 min

Linked lists

Why this matters

A dynamic array keeps elements side by side, so inserting in the middle means shifting everything after it, and growing may move the whole block. A linked list makes the opposite trade: each element lives in its own small heap allocation and points to the next one. Inserting or removing anywhere you already have a pointer is two pointer assignments, and elements never move. Linked lists appear throughout systems code: the Linux kernel's process list, free lists inside malloc, hash table buckets (next-but-one lesson), and LRU caches. More importantly for you, they are the best exercise there is in pointer manipulation. If you can write list code correctly, pointers no longer scare you.

Nodes and the head pointer

A list is built from nodes. Each node holds a value and a pointer to the next node; the last node's pointer is NULL:

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

The struct refers to itself: next is a pointer to another struct Node. Inside the definition the typedef name Node does not exist yet, which is why the member is written struct Node *. A struct cannot contain itself (it would be infinitely large), but it can contain a pointer to its own type, which is just 8 bytes.

The list as a whole is represented by a single pointer to the first node, the head. An empty list is a head of NULL.

  head
  +---+     +-------+---+     +-------+---+     +-------+------+
  | o-+---> | 40    | o-+---> | 30    | o-+---> | 20    | NULL |
  +---+     +-------+---+     +-------+---+     +-------+------+
  (stack)    node (heap)       node (heap)       node (heap)

The nodes are separate malloc blocks, anywhere in the heap. The only thing connecting them is the next pointers.

Building, walking and freeing

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

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

/* Add a node at the front. Returns the new head, or NULL if out of memory. */
Node *push_front(Node *head, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return NULL;
    n->value = value;
    n->next = head;
    return n;
}

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

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

push_front is O(1): the new node points at the old head and becomes the new head. Draw it:

  before:  head -> [30] -> [20] -> NULL
  n = malloc, n->value = 40, n->next = head:
           n -> [40] -> [30] -> [20] -> NULL
  return n; caller stores it in head

Traversal is the loop for (p = head; p != NULL; p = p->next), which you will write constantly. Read it as "start at the head, stop at the end, step along the links".

free_list must save head->next before freeing head, because after free the node's contents may not be read. Every node was a separate malloc, so every node needs its own free.

Changing the head: pointers to pointers

push_front returns the new head, and the caller must remember to store it. Functions that may change the head (removing the first node, appending to an empty list) can instead take the address of the caller's head pointer, a Node **:

/* Remove the first node holding value. Returns 1 if one was removed. */
int remove_value(Node **headp, int value)
{
    for (Node **pp = headp; *pp != NULL; pp = &(*pp)->next) {
        if ((*pp)->value == value) {
            Node *victim = *pp;
            *pp = victim->next;     /* unlink: whoever pointed at victim now skips it */
            free(victim);
            return 1;
        }
    }
    return 0;
}

This is worth slowing down for. pp does not point at nodes; it points at the pointer that points at the current node. At first that is the caller's head variable itself; after one step it is the first node's next field; and so on.

  pp starts at &head:

  head            node A           node B           node C
  +---+          +----+---+       +----+---+       +----+------+
  | o-+--------> | 40 | o-+-----> | 30 | o-+-----> | 20 | NULL |
  +---+          +----+---+       +----+---+       +----+------+
    ^                   ^
    pp (first)          pp (after one step) = &A->next

  removing node B when pp == &A->next:
    victim = *pp          (B)
    *pp = victim->next    (A->next now points at C)
    free(victim)

Because removing the head is just "the pointer that points at the head is head itself", the same three lines handle the first node, a middle node and the last node. No special case. Linus Torvalds has called this the mark of someone who understands pointers.

Using everything together:

int main(void)
{
    Node *head = NULL;
    for (int i = 1; i <= 4; i++) {
        Node *n = push_front(head, i * 10);
        if (n == NULL) {
            free_list(head);
            return 1;
        }
        head = n;
    }
    print_list(head);
    remove_value(&head, 40);   /* the head */
    remove_value(&head, 20);   /* the tail */
    print_list(head);
    free_list(head);
    return 0;
}

40 -> 30 -> 20 -> 10 -> NULL
30 -> 10 -> NULL

valgrind reports no errors and no leaks.

Variations

Tail pointer. Appending to a list with only a head is O(n): you must walk to the end. Keep a second pointer to the last node (often in a small List struct with head, tail and len) to make appends O(1). That is how queues are built in the next lesson.
Doubly linked list. Each node also has prev. Removal of a node you hold becomes O(1) without needing its predecessor, at the cost of another pointer per node and more links to keep consistent.
Intrusive lists. The Linux kernel embeds a struct list_head { next, prev } inside its own structs instead of allocating separate nodes, so one object can sit in several lists without extra allocations.

Common mistakes

Using a node after freeing it, most often in the free loop itself. valgrind: Invalid read of size 8 ... Address ... is 8 bytes inside a block of size 16 free'd.
Losing the rest of the list. Overwriting head->next before saving it orphans every node after it: a leak valgrind reports as "indirectly lost".
Forgetting to update the caller's head. push_front(head, 5); without head = ... leaks the new node and the list is unchanged. Passing Node ** avoids the problem.
Not handling the empty list. Code that does head->next without checking head != NULL crashes with a segmentation fault on empty input.
Uninitialized next. A node from malloc has a garbage next; always set it, usually to NULL or the old head.

Recap

A node holds a value and a next pointer; the list is a head pointer, NULL when empty.
Traverse with for (p = head; p != NULL; p = p->next).
Free node by node, saving next before each free.
Functions that may change the head take Node **; walking a Node **pp handles every position uniformly.
Lists give O(1) splicing and stable node addresses; arrays give O(1) indexing and cache-friendly traversal.

Going further: implement a doubly linked list with insert_after and remove_node, and test it under valgrind. Then look up Floyd's "tortoise and hare" algorithm for detecting a cycle in a list using two pointers moving at different speeds.

Exercises

Exercise 1 · quiz

Array or list?

Compare a singly linked list (with only a head pointer) to a dynamic array holding the same n elements. Which statements are true? Select all that apply.

Reading the element at index k is O(1) for the array and O(k) for the list
Inserting at the front is O(1) for the list and O(n) for the array
The list uses less memory per element than the array
Inserting after a node you already have a pointer to is O(1) for the list
Walking through all elements is usually faster for the array because its elements are contiguous in memory

Answer

Reading the element at index k is O(1) for the array and O(k) for the list
Inserting at the front is O(1) for the list and O(n) for the array
Inserting after a node you already have a pointer to is O(1) for the list
Walking through all elements is usually faster for the array because its elements are contiguous in memory

The list must follow k next pointers to reach index k. It wins at the front and anywhere you already hold a node: splicing in a node is two pointer assignments, with no shifting. It costs more memory (a pointer per element, plus malloc's own bookkeeping per node), and its nodes are scattered across the heap, so traversal misses the CPU cache far more often than scanning an array. In practice dynamic arrays win more often than textbooks suggest; lists shine when elements must keep stable addresses or be spliced in and out in O(1).

Exercise 2 · quiz

Freeing while walking

What is wrong with this function?

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

Nothing
After free(p), the loop reads p->next: that is a use after free
It frees the nodes in the wrong order and leaks the last one
free cannot be called inside a loop

Answer

After free(p), the loop reads p->next: that is a use after free

The increment p = p->next runs after the body, so it reads a field of a node that was just freed. It often appears to work because free does not erase memory, but it is undefined behavior and valgrind reports "Invalid read of size 8 ... inside a block of size 16 free'd". Save the next pointer first: Node *next = p->next; free(p); p = next;.

Exercise 3 · write code

Count and clean up

The starter builds a list by pushing every number from stdin onto the front, then prints it and its length. list_length and free_list are wrong. Fix both:

size_t list_length(const Node *head) returns the number of nodes.
void free_list(Node *head) frees every node, without touching a node after freeing it.

The check runs the program and a test harness under valgrind, so leaks and invalid reads fail it.

$ echo "1 2 3" | ./prog
3 -> 2 -> 1 -> NULL
length 3

File: main.c

Starting point

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

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

Node *push_front(Node *head, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return NULL;
    n->value = value;
    n->next = head;
    return n;
}

size_t list_length(const Node *head)
{
    return head != NULL;
}

void free_list(Node *head)
{
    free(head);
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1) {
        Node *n = push_front(head, x);
        if (n == NULL) {
            free_list(head);
            return 1;
        }
        head = n;
    }
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\nlength %zu\n", list_length(head));
    free_list(head);
    return 0;
}

Example

input

1 2 3

expected output

3 -> 2 -> 1 -> NULL
length 3

Hint 1

Both functions walk the list with a pointer that starts at head and follows ->next until NULL.

Hint 2

In free_list, save head->next in a variable before calling free(head).

Reference solution

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

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

Node *push_front(Node *head, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return NULL;
    n->value = value;
    n->next = head;
    return n;
}

size_t list_length(const Node *head)
{
    size_t n = 0;
    for (const Node *p = head; p != NULL; p = p->next)
        n++;
    return n;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1) {
        Node *n = push_front(head, x);
        if (n == NULL) {
            free_list(head);
            return 1;
        }
        head = n;
    }
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\nlength %zu\n", list_length(head));
    free_list(head);
    return 0;
}

Exercise 4 · write code

Append with a pointer to a pointer

Write int append(Node **headp, int value), which adds a new node at the end of the list and returns 0, or returns -1 if malloc fails. It must work when the list is empty, which means it may have to change the caller's head pointer: that is why it receives Node **.

Do it without a special case for the empty list, by walking a Node **pp from headp to the next field of the last node (the NULL slot), as remove_value does in the lesson.

main appends every number from stdin and prints the list:

$ echo "1 2 3" | ./prog
1 -> 2 -> 3 -> NULL

File: main.c

Starting point

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

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

int append(Node **headp, int value)
{
    return -1;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1)
        if (append(&head, x) != 0) {
            free_list(head);
            return 1;
        }
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\n");
    free_list(head);
    return 0;
}

Example

input

1 2 3

expected output

1 -> 2 -> 3 -> NULL

Example

expected output

NULL

Hint 1

pp starts as headp, the address of the caller's head. While *pp is not NULL, move to the address of that node's next field: pp = &(*pp)->next;

Hint 2

When the loop ends, *pp is the NULL slot where the new node belongs: allocate it, set next to NULL, and store it with *pp = n.

Reference solution

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

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

int append(Node **headp, int value)
{
    Node **pp = headp;
    while (*pp != NULL)
        pp = &(*pp)->next;
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return -1;
    n->value = value;
    n->next = NULL;
    *pp = n;
    return 0;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1)
        if (append(&head, x) != 0) {
            free_list(head);
            return 1;
        }
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\n");
    free_list(head);
    return 0;
}

Exercise 5 · write code

Reverse in place

Write Node *reverse(Node *head) that reverses the list in place by relinking the existing nodes (no malloc, no free, no copying values) and returns the new head. It must handle the empty list and a single node.

Walk the list once with three pointers: the part already reversed (prev), the current node, and the next node you are about to lose track of. Draw it on paper first.

main appends the numbers from stdin, reverses, and prints:

$ echo "1 2 3 4" | ./prog
4 -> 3 -> 2 -> 1 -> NULL

File: main.c

Starting point

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

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

Node *reverse(Node *head)
{
    return head;
}

int append(Node **headp, int value)
{
    Node **pp = headp;
    while (*pp != NULL)
        pp = &(*pp)->next;
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return -1;
    n->value = value;
    n->next = NULL;
    *pp = n;
    return 0;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1)
        if (append(&head, x) != 0) {
            free_list(head);
            return 1;
        }
    head = reverse(head);
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\n");
    free_list(head);
    return 0;
}

Example

input

1 2 3 4

expected output

4 -> 3 -> 2 -> 1 -> NULL

Example

input

expected output

9 -> NULL

Hint 1

Start with prev = NULL. For each node: save next = head->next, then set head->next = prev.

Hint 2

Then advance: prev = head; head = next. When head is NULL, prev is the new head.

Reference solution

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

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

Node *reverse(Node *head)
{
    Node *prev = NULL;
    while (head != NULL) {
        Node *next = head->next;   /* remember the rest */
        head->next = prev;         /* point this node backwards */
        prev = head;               /* reversed part now starts here */
        head = next;               /* move on */
    }
    return prev;
}

int append(Node **headp, int value)
{
    Node **pp = headp;
    while (*pp != NULL)
        pp = &(*pp)->next;
    Node *n = malloc(sizeof *n);
    if (n == NULL)
        return -1;
    n->value = value;
    n->next = NULL;
    *pp = n;
    return 0;
}

void free_list(Node *head)
{
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
}

int main(void)
{
    Node *head = NULL;
    int x;
    while (scanf("%d", &x) == 1)
        if (append(&head, x) != 0) {
            free_list(head);
            return 1;
        }
    head = reverse(head);
    for (const Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->value);
    printf("NULL\n");
    free_list(head);
    return 0;
}