Linked lists

Lesson 26 of 30 · Part 5 · Your own types · about 20 minutes

The elements of an array sit one right after another. To add one at the front, everything behind it has to move over by one; when it's full, you have to realloc a bigger block (lesson 22). A linked list works differently: each item sits in its own small box, called a node, and besides its value, each node remembers where the next node is. To add an item, you make a new node and change one or two pointers, and no other node moves at all.

This lesson uses a shopping list as its example. When you press Step, the list is drawn as a row of boxes joined by arrows.

The node

A node is a struct: one member holds the value, and one is a pointer to the next node.

main.c

1#include <stdio.h>2 3typedef struct node {4    char item[16];5    struct node *next;6} Node;7 8int main(void) {9    Node c = { "Eggs", NULL };10    Node b = { "Bread", &c };11    Node a = { "Milk", &b };12    Node *head = &a;13    for (Node *p = head; p != NULL; p = p->next) {14        printf("%s\n", p->item);15    }16    return 0;17}

Output

Milk
Bread
Eggs

Press Step and watch the three boxes get joined: the next of a points to b, the one of b points to c, and the next of c is NULL, meaning the list ends there. head points to the first node, and from it you can reach the whole list.

Notice that the struct says struct node *next, not Node *next: on that line the typedef isn't finished yet, so the name Node doesn't exist. That's what the last lesson meant by "a struct that refers to itself needs a name before the curly brace".

Walking the list

A linked list has no indexes; you can't write list[2]. To find the third item, you have to start at head and follow next one node at a time. The for above is the standard way to walk a list:

Part	Meaning
`Node *p = head`	start at the first node
`p != NULL`	keep going until you reach the end
`p = p->next`	move on to the next node

Put it in a function, and you can print the whole list or count how long it is. The function gets the address of a node and walks on from whichever node you give it:

main.c

1#include <stdio.h>2 3typedef struct node {4    char item[16];5    struct node *next;6} Node;7 8void print_list(Node *head) {9    for (Node *p = head; p != NULL; p = p->next) {10        printf("%s -> ", p->item);11    }12    printf("NULL\n");13}14 15int count(Node *head) {16    int n = 0;17    for (Node *p = head; p != NULL; p = p->next) {18        n++;19    }20    return n;21}22 23int main(void) {24    Node c = { "Eggs", NULL };25    Node b = { "Bread", &c };26    Node a = { "Milk", &b };27    print_list(&a);28    printf("%d items\n", count(&a));29    print_list(&b);30    return 0;31}

Output

Milk -> Bread -> Eggs -> NULL
3 items
Bread -> Eggs -> NULL

What if you walk past the end? The list has only two items, and we try to change the third one to Eggs:

main.c

1#include <stdio.h>2#include <string.h>3 4typedef struct node {5    char item[16];6    struct node *next;7} Node;8 9int main(void) {10    Node b = { "Bread", NULL };11    Node a = { "Milk", &b };12    Node *head = &a;13    strcpy(head->next->next->item, "Eggs");14    return 0;15}

Output

store to null pointer

What happened: Stopped at line 13. This pointer is NULL: nothing can be read or written through it.

head->next is b, the next of b is NULL, and ->item after that means writing into NULL, which points to no node at all. Our engine stops on this line; on a real computer the program usually crashes. Press "see how it went wrong", follow the arrows, and see where the last step lands.

Nodes on the heap

So far the nodes were local variables in main, and how many there are was fixed in the code. In real use, a list's nodes are made one at a time while the program runs, so they go on the heap. A function that makes a node:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19int main(void) {20    Node *a = new_node("Milk");21    Node *b = new_node("Bread");22    Node *c = new_node("Eggs");23    a->next = b;24    b->next = c;25    for (Node *p = a; p != NULL; p = p->next) {26        printf("%s\n", p->item);27    }28    free(a);29    free(b);30    free(c);31    return 0;32}

Output

Milk
Bread
Eggs

Press Step: each call to new_node adds a box on the heap, with next set to NULL. At a->next = b;, an arrow appears from the first box to the second. At the end, the three free calls give the boxes back one by one.

Tip: To keep the examples short, some places in this lesson don't check whether malloc or new_node returned NULL. A real program should.

Freeing it all

With many nodes, you can't write one free per node: you walk the list and free as you go. But the most natural way to write it is wrong:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19int main(void) {20    Node *head = new_node("Milk");21    head->next = new_node("Bread");22    for (Node *p = head; p != NULL; p = p->next) {23        free(p);24    }25    return 0;26}

Output

heap-use-after-free

What happened: Stopped at line 22. This memory is no longer yours: it was freed, or it belonged to a function that has returned.

After free(p), the for goes on to p = p->next, but the box p points to was just given back. That is using memory after it's freed (lesson 21). The engine stops on this line; press "see how it went wrong".

The fix: before you free a node, save the address of the next one:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19void free_list(Node *head) {20    while (head != NULL) {21        Node *next = head->next;22        free(head);23        head = next;24    }25}26 27int main(void) {28    Node *head = new_node("Milk");29    head->next = new_node("Bread");30    head->next->next = new_node("Eggs");31    printf("3 items, freeing them all now\n");32    free_list(head);33    return 0;34}

Output

3 items, freeing them all now

Press Step and watch the front box turn gray, marked "freed", again and again, with head moving along until it becomes NULL.

Inserting at the front and in the middle

Adding at the front is the easiest: point the new node's next at the old first node, and the new node becomes the new head. The function returns the new head, and the caller stores it:

Guess first

What does this program print?

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *push_front(Node *head, const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = head;14    return n;15}16 17void free_list(Node *head) {18    while (head != NULL) {19        Node *next = head->next;20        free(head);21        head = next;22    }23}24 25int main(void) {26    Node *list = NULL;27    list = push_front(list, "Milk");28    list = push_front(list, "Bread");29    list = push_front(list, "Eggs");30    for (Node *p = list; p != NULL; p = p->next) {31        printf("%s ", p->item);32    }33    printf("\n");34    free_list(list);35    return 0;36}

Each item goes in at the front, so the last one added comes first: first Milk, then Bread goes in front of it, then Eggs in front of Bread. However long the list is, inserting at the front changes just two pointers and moves no other node.

Output

Inserting in the middle also takes just two pointer changes. insert_after below links a new node in after prev:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    if (n != NULL) {13        strcpy(n->item, item);14        n->next = NULL;15    }16    return n;17}18 19void insert_after(Node *prev, const char *item) {20    Node *n = new_node(item);21    n->next = prev->next;22    prev->next = n;23}24 25void print_list(Node *head) {26    for (Node *p = head; p != NULL; p = p->next) {27        printf("%s -> ", p->item);28    }29    printf("NULL\n");30}31 32void free_list(Node *head) {33    while (head != NULL) {34        Node *next = head->next;35        free(head);36        head = next;37    }38}39 40int main(void) {41    Node *head = new_node("Milk");42    head->next = new_node("Eggs");43    print_list(head);44    insert_after(head, "Bread");45    print_list(head);46    free_list(head);47    return 0;48}

Output

Milk -> Eggs -> NULL
Milk -> Bread -> Eggs -> NULL

Press Step, go into insert_after and watch the two steps: first the new node points to Eggs, then Milk switches to point at the new node. The order can't be swapped: if you changed prev->next first, the address of Eggs would be lost, and the rest of the list with it.

Removing a node

Removing is changing pointers too: make the node before it skip over it and point straight to the one after, then free it. When the node to remove is the first one, there is no node before it, so head changes instead:

main.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *push_front(Node *head, const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = head;14    return n;15}16 17Node *remove_item(Node *head, const char *item) {18    Node *prev = NULL;19    Node *p = head;20    while (p != NULL && strcmp(p->item, item) != 0) {21        prev = p;22        p = p->next;23    }24    if (p == NULL) {25        return head;26    }27    if (prev == NULL) {28        head = p->next;29    } else {30        prev->next = p->next;31    }32    free(p);33    return head;34}35 36void print_list(Node *head) {37    for (Node *p = head; p != NULL; p = p->next) {38        printf("%s -> ", p->item);39    }40    printf("NULL\n");41}42 43int main(void) {44    Node *list = NULL;45    list = push_front(list, "Eggs");46    list = push_front(list, "Bread");47    list = push_front(list, "Milk");48    print_list(list);49    list = remove_item(list, "Bread");50    print_list(list);51    list = remove_item(list, "Milk");52    print_list(list);53    list = remove_item(list, "Eggs");54    print_list(list);55    return 0;56}

Output

Milk -> Bread -> Eggs -> NULL
Milk -> Eggs -> NULL
Eggs -> NULL
NULL

The while searches and keeps track of the node before, prev, as it goes. If the item isn't there (p reaches NULL), nothing changes. Press Step and watch, when Bread is removed, the arrow from Milk go around it straight to Eggs, and then the Bread box turn gray, marked "freed". When the last item is removed too, list is back to NULL, and an empty list prints as just NULL.

Practice

Write the code, then press Check. A hint costs nothing; the answer is there when you need it.

Exercise 1

The total

Each node is the price of one item. Walk the list, add up the prices, and print Total: 23.50.

It should print

Total: 23.50

exercise1.c

1#include <stdio.h>2 3typedef struct node {4    double price;5    struct node *next;6} Node;7 8int main(void) {9    Node c = { 4.5, NULL };10    Node b = { 12.0, &c };11    Node a = { 7.0, &b };12    Node *head = &a;13 14    return 0;15}

Output

Press Run or Ctrl+Enter

Exercise 2

Is it on the list?

Write a function contains that returns 1 if item is on the list and 0 if it isn't. The program should print Bread: 1 and Butter: 0.

It should print

Bread: 1
Butter: 0

exercise2.c

1#include <stdio.h>2#include <string.h>3 4typedef struct node {5    char item[16];6    struct node *next;7} Node;8 9int contains(Node *head, const char *item) {10 11}12 13int main(void) {14    Node c = { "Eggs", NULL };15    Node b = { "Bread", &c };16    Node a = { "Milk", &b };17    printf("Bread: %d\n", contains(&a, "Bread"));18    printf("Butter: %d\n", contains(&a, "Butter"));19    return 0;20}

Output

Press Run or Ctrl+Enter

Exercise 3

Add to the end

Write a function push_back that links a new node onto the end of the list and returns head. When the list is empty (head is NULL), the new node is the head. The program should print Milk -> Bread -> Eggs -> NULL.

It should print

Milk -> Bread -> Eggs -> NULL

exercise3.c

1#include <stdio.h>2#include <stdlib.h>3#include <string.h>4 5typedef struct node {6    char item[16];7    struct node *next;8} Node;9 10Node *new_node(const char *item) {11    Node *n = malloc(sizeof(Node));12    strcpy(n->item, item);13    n->next = NULL;14    return n;15}16 17Node *push_back(Node *head, const char *item) {18 19}20 21void free_list(Node *head) {22    while (head != NULL) {23        Node *next = head->next;24        free(head);25        head = next;26    }27}28 29int main(void) {30    Node *list = NULL;31    list = push_back(list, "Milk");32    list = push_back(list, "Bread");33    list = push_back(list, "Eggs");34    for (Node *p = list; p != NULL; p = p->next) {35        printf("%s -> ", p->item);36    }37    printf("NULL\n");38    free_list(list);39    return 0;40}

Output

Press Run or Ctrl+Enter

What you learned

A linked list is made of nodes: each holds a value and a next pointer, the last one's next is NULL, and head points to the first.
The node struct uses struct node *next, because the typedef name doesn't exist yet at that point.
Walk a list with for (Node *p = head; p != NULL; p = p->next). There are no indexes, only one node after another from the start; walking past the end hits NULL.
Nodes are made on the heap with malloc; inserting at the front, inserting in the middle and removing one each change only one or two pointers, and no other node moves.
The order of pointer changes matters: when inserting, link up the rest of the list first, then change the node before.
To free a whole list, save next before each free, or you're using memory that was already freed.