Singly linked lists

Introduction

In the C course you built a list by inserting at the front. A real list also needs to add at the end, find a value and delete a node. All three are about one thing: keeping the chain of next pointers joined.

A linked list trades the array's instant indexing for something else: nodes can sit anywhere in memory, so the list can grow one node at a time and never needs shifting. The price is that the only way to reach a node is to walk there.

How it works

Appending with a tail pointer

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

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

Node *new_node(int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = NULL;
    return n;
}

int main(void) {
    Node *head = NULL, *tail = NULL;
    for (int v = 1; v <= 3; v++) {
        Node *n = new_node(v * 10);
        if (head == NULL) head = n;
        else tail->next = n;
        tail = n;
    }
    for (Node *p = head; p != NULL; p = p->next) printf("%d -> ", p->value);
    printf("NULL\n");
    while (head != NULL) {
        Node *next = head->next;
        free(head);
        head = next;
    }
    return 0;
}

Walking to the end before each append would cost O(n). Keeping a second pointer, tail, at the last node makes appending O(1): link the old tail to the new node, then move tail. The first node is a special case, because there is no old tail: both head and tail point to it.

typedef struct node { ... } Node; lets us write Node instead of struct node. The struct still needs its tag node inside, for the next field.

Syntax

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

Node *n = malloc(sizeof(Node));   // one new node on the heap
n->value = 7;
n->next = head;                   // point it at the old first node
head = n;                         // it is the new first node

Example

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

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

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

Node *delete_value(Node *head, int value) {
    Node *prev = NULL, *cur = head;
    while (cur != NULL && cur->value != value) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return head;          // not in the list
    if (prev == NULL) head = cur->next;    // deleting the first node
    else prev->next = cur->next;
    free(cur);
    return head;
}

int main(void) {
    Node *head = NULL;
    for (int v = 40; v >= 10; v -= 10) head = push(head, v);
    head = delete_value(head, 30);
    head = delete_value(head, 10);
    for (Node *p = head; p != NULL; p = p->next) printf("%d ", p->value);
    printf("\n");
    return 0;
}

To remove a node, the node before it must skip over it: prev->next = cur->next. So the search loop moves two pointers, prev and cur, one step apart. Watch the arrows in the visualizer:

1. Find the node: stop when cur->value == value, or at NULL if it is not there.
2. Unlink it: if prev is NULL, the node is the head, so head moves instead.
3. free(cur), and return the (possibly new) head.

Line by line

1. Node holds a value and a pointer to the next node, and NULL marks the end of the chain.
2. push makes a node, points it at the old head and returns it as the new head.
3. In delete_value, the while loop moves prev and cur together until cur holds the value or falls off the end.
4. If cur is NULL, the value is absent and the list is returned unchanged.
5. If prev is NULL the first node is going, so head moves. Otherwise prev->next skips over cur.
6. free(cur) releases the node only after the chain has been joined around it.
7. main builds 10, 20, 30, 40, deletes 30 from the middle and 10 from the front, and prints what is left.

Expected result

20 40 

In the real world

Operating systems keep lists of running processes and free memory blocks. Many of those lists are linked, because an item often has to be removed from the middle at a moment when shifting a whole array would be far too slow.

Common mistakes

• Deleting the head without moving head: the caller still points to freed memory.
• Freeing a node before linking around it: prev->next = cur->next must come first.
• Forgetting tail when the last node is deleted or the list becomes empty.

Best practices

• Draw the nodes and arrows on paper before writing the pointer changes.
• Test each operation on an empty list, a one-node list, and at both ends.
• Free every node you allocate, and save next before freeing.

Summary

A singly linked list is a chain of heap nodes. Adding at a known place is O(1), finding a value is O(n), and deleting means making the previous node skip over the one being removed.

Mark lesson complete