Linked Data Structures

1The node

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

Each node holds its data and the address of the next. The list itself is just a pointer to the first node; the end is marked by a next of NULL.

2Insertion and removal

/* At the front: O(1) */
bool push_front(Node **head, int value)
{
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false;
    node->value = value;
    node->next  = *head;
    *head = node;                     /* modifies the caller's pointer */
    return true;
}

Note the Node **. The function must change the caller's head, so it takes its address — week 15's pointer-to-pointer, in its most common real use.

Removal, and the special case

Written naively, removal needs a separate branch for the head:

void remove_value(Node **head, int value)
{
    if (*head == NULL) return;

    if ((*head)->value == value) {     /* special case */
        Node *dead = *head;
        *head = dead->next;
        free(dead);
        return;
    }
    Node *prev = *head;                /* general case */
    while (prev->next != NULL && prev->next->value != value) {
        prev = prev->next;
    }
    if (prev->next != NULL) {
        Node *dead = prev->next;
        prev->next = dead->next;
        free(dead);
    }
}

The special case exists because the head is stored in a different kind of place from every other link. Track a pointer to the pointer instead and the distinction vanishes:

void remove_value(Node **head, int value)
{
    for (Node **link = head; *link != NULL; link = &(*link)->next) {
        if ((*link)->value == value) {
            Node *dead = *link;
            *link = dead->next;
            free(dead);
            return;
        }
    }
}

link points at whatever holds the address of the current node — the caller's head for the first, the previous node's next thereafter. Writing through it updates the right place either way. Half the code, no branch, and no way to get the head case wrong.

3Doubly linked and circular

typedef struct DNode {
    int           value;
    struct DNode *prev;
    struct DNode *next;
} DNode;

A backward link costs one pointer per node and buys two things: traversal in both directions, and removal of a node in O(1) when you already hold it — no search for the predecessor.

void dlist_remove(DList *l, DNode *node)
{
    if (node->prev != NULL) node->prev->next = node->next;
    else                    l->head          = node->next;

    if (node->next != NULL) node->next->prev = node->prev;
    else                    l->tail          = node->prev;

    free(node);
}

The two special cases are back. A circular list with a sentinel removes them: a permanent dummy node whose next and prev close the ring, so every real node always has both neighbours.

/* with a sentinel, removal has no branches at all */
node->prev->next = node->next;
node->next->prev = node->prev;
free(node);

This is how the Linux kernel's list_head works, and it is the reason its list code has no null checks. The cost is one node's worth of memory per list.

4Stacks and queues

Both are lists with a restricted interface — which is the point: the restriction is what makes the structure useful.

A queue without a tail pointer makes enqueue O(n), because every insertion walks to the end. Keeping a tail pointer is the whole design decision — and the thing to get right is updating it when the list becomes empty.

5When a list actually wins

Read the fifth row carefully. The textbook claim that lists are better for middle insertion assumes you already hold a pointer to the position. If you have to find it first, the search dominates and both are O(n) — and the array is faster in practice because the traversal is sequential.

That is why, on modern hardware, an array wins far more often than complexity tables suggest. Each list node is a separate allocation, typically 32 bytes for 4 bytes of data, scattered across memory so that every step is a potential cache miss. Week 34 measures this directly.

Use a linked list when you hold pointers to elements and splice them between containers, when elements must not move because other things point at them, when you are building an intrusive structure as the kernel does, or when a stack or queue is all you need. Otherwise start with an array.

6Worked example: list, stack, queue, and a measurement

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

/* ================= singly linked list ================= */

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

typedef struct {
    Node   *head;
    Node   *tail;          /* for O(1) append and enqueue */
    size_t  count;
} List;

static void list_init(List *l)
{
    l->head = l->tail = NULL;
    l->count = 0;
}

static void list_destroy(List *l)
{
    Node *n = l->head;
    while (n != NULL) {
        Node *next = n->next;      /* save before freeing */
        free(n);
        n = next;
    }
    list_init(l);
}

static bool list_push_front(List *l, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->value = value;
    n->next  = l->head;
    l->head  = n;
    if (l->tail == NULL) l->tail = n;      /* first node is also the tail */
    l->count++;
    return true;
}

static bool list_push_back(List *l, int value)
{
    Node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->value = value;
    n->next  = NULL;
    if (l->tail != NULL) l->tail->next = n;
    else                 l->head       = n;
    l->tail = n;
    l->count++;
    return true;
}

/* The pointer-to-pointer idiom: no special case for the head. */
static bool list_remove(List *l, int value)
{
    for (Node **link = &l->head; *link != NULL; link = &(*link)->next) {
        if ((*link)->value == value) {
            Node *dead = *link;
            *link = dead->next;
            if (dead == l->tail) {
                l->tail = (link == &l->head) ? NULL : (Node *)((char *)link -
                          offsetof(Node, next));
            }
            free(dead);
            l->count--;
            return true;
        }
    }
    return false;
}

/* Reverse in place: three pointers, one pass, no allocation. */
static void list_reverse(List *l)
{
    Node *prev = NULL;
    Node *curr = l->head;
    l->tail = l->head;
    while (curr != NULL) {
        Node *next = curr->next;   /* save the rest */
        curr->next = prev;          /* flip this link */
        prev = curr;                /* advance */
        curr = next;
    }
    l->head = prev;
}

static void list_print(const List *l, const char *label)
{
    printf("  %-12s (%zu)", label, l->count);
    for (const Node *n = l->head; n != NULL; n = n->next) {
        printf(" %d", n->value);
    }
    putchar('\n');
}

/* ================= stack ================= */

typedef struct { List inner; } Stack;

static void stack_init(Stack *s)    { list_init(&s->inner); }
static void stack_destroy(Stack *s) { list_destroy(&s->inner); }
static bool stack_push(Stack *s, int v) { return list_push_front(&s->inner, v); }

static bool stack_pop(Stack *s, int *out)
{
    Node *top = s->inner.head;
    if (top == NULL) return false;
    *out = top->value;
    s->inner.head = top->next;
    if (s->inner.head == NULL) s->inner.tail = NULL;
    free(top);
    s->inner.count--;
    return true;
}

/* ================= queue ================= */

typedef struct { List inner; } Queue;

static void queue_init(Queue *q)    { list_init(&q->inner); }
static void queue_destroy(Queue *q) { list_destroy(&q->inner); }
static bool queue_enqueue(Queue *q, int v) { return list_push_back(&q->inner, v); }

static bool queue_dequeue(Queue *q, int *out)
{
    Node *front = q->inner.head;
    if (front == NULL) return false;
    *out = front->value;
    q->inner.head = front->next;
    if (q->inner.head == NULL) q->inner.tail = NULL;
    free(front);
    q->inner.count--;
    return true;
}

/* ================= measurement ================= */

#define N 200000

static double time_list_traversal(void)
{
    List l;
    list_init(&l);
    for (int i = 0; i < N; i++) list_push_front(&l, i);

    clock_t t0 = clock();
    long sum = 0;
    for (int pass = 0; pass < 20; pass++) {
        for (const Node *n = l.head; n != NULL; n = n->next) sum += n->value;
    }
    double secs = (double)(clock() - t0) / CLOCKS_PER_SEC;
    printf("    (list sum %ld)\n", sum);
    list_destroy(&l);
    return secs;
}

static double time_array_traversal(void)
{
    int *a = malloc(N * sizeof *a);
    if (a == NULL) return -1.0;
    for (int i = 0; i < N; i++) a[i] = i;

    clock_t t0 = clock();
    long sum = 0;
    for (int pass = 0; pass < 20; pass++) {
        for (int i = 0; i < N; i++) sum += a[i];
    }
    double secs = (double)(clock() - t0) / CLOCKS_PER_SEC;
    printf("    (array sum %ld)\n", sum);
    free(a);
    return secs;
}

int main(void)
{
    puts("== list operations ==");
    List l;
    list_init(&l);
    for (int i = 1; i <= 5; i++) list_push_back(&l, i * 10);
    list_print(&l, "built");

    list_push_front(&l, 5);
    list_print(&l, "push_front");

    printf("  remove 30: %s\n", list_remove(&l, 30) ? "yes" : "no");
    list_print(&l, "after");

    printf("  remove 5 (the head): %s\n", list_remove(&l, 5) ? "yes" : "no");
    list_print(&l, "after");
    puts("  no special case was needed for the head");

    printf("  remove 999: %s\n", list_remove(&l, 999) ? "yes" : "no");

    list_reverse(&l);
    list_print(&l, "reversed");

    list_destroy(&l);

    puts("\n== stack: last in, first out ==");
    Stack s;
    stack_init(&s);
    for (int i = 1; i <= 4; i++) {
        stack_push(&s, i);
        printf("  pushed %d\n", i);
    }
    int v;
    while (stack_pop(&s, &v)) printf("  popped %d\n", v);
    printf("  pop on empty: %s\n", stack_pop(&s, &v) ? "value" : "refused");
    stack_destroy(&s);

    puts("\n== queue: first in, first out ==");
    Queue q;
    queue_init(&q);
    for (int i = 1; i <= 4; i++) {
        queue_enqueue(&q, i);
        printf("  enqueued %d\n", i);
    }
    while (queue_dequeue(&q, &v)) printf("  dequeued %d\n", v);
    queue_destroy(&q);

    puts("\n== traversal: list versus array ==");
    double list_secs  = time_list_traversal();
    double array_secs = time_array_traversal();
    printf("  %d elements, 20 passes\n", N);
    printf("  linked list : %.4f s\n", list_secs);
    printf("  array       : %.4f s\n", array_secs);
    if (array_secs > 0) {
        printf("  the array is %.1fx faster for the same operation count\n",
               list_secs / array_secs);
    }
    puts("  same asymptotic complexity; the difference is cache locality");

    printf("\n  memory per element: array %zu bytes, list node %zu bytes\n",
           sizeof(int), sizeof(Node));
    puts("  plus allocator overhead of roughly 16 bytes per node");

    return EXIT_SUCCESS;
}

The list_remove tail fix-up above uses offsetof, which needs <stddef.h>. In production code a doubly linked list avoids the gymnastics entirely; the version here is deliberately kept singly linked to show the pointer-to-pointer idiom in isolation.

gcc -std=c17 -Wall -Wextra -g -fsanitize=address -o lists lists.c
./lists

What the measurement shows

Both traversals are O(n) and execute the same number of additions. The array is typically three to ten times faster. Nothing about the algorithm differs — the array's elements are contiguous, so each cache line fetch brings sixteen integers, while each list node is a separate allocation and every step is a potential cache miss.

The memory figures make the same point from the other side: 4 bytes of data per element in the array, against 16 bytes of node plus roughly 16 bytes of allocator bookkeeping in the list. Eight times the memory for the same information.

This is why "use a linked list for frequent insertion" is bad advice without qualification. Measure before choosing, and week 34 shows how.

Verify the idiom removes the branch

Rewrite list_remove with the naive head special case, then run both against these four inputs: removing the head, removing a middle node, removing the tail, and removing from an empty list. Both versions must behave identically — and the pointer-to-pointer version is half the length with no branch to get wrong.

Check for leaks deliberately

Delete the list_destroy(&l) call and rerun:

==1234==ERROR: LeakSanitizer: detected memory leaks
Direct leak of 96 byte(s) in 6 object(s) allocated from:
    #1 0x... in list_push_back lists.c:52

Every node is a separate allocation, so a list is the structure most likely to leak. The init/destroy pairing from week 19 is not optional here.

7Common mistakes

9Where this leads

Week 33 adds the structures where the pointer work pays off: binary search trees, where recursion from week 18 becomes indispensable, and hash tables, which give constant-time lookup. Both go behind the opaque interface of week 28, and the complexity reasoning that this week's measurement started gets its proper vocabulary.