Linked Lists in C

The Node and Three Helpers

A singly linked list is a chain of heap-allocated nodes, each holding data and a pointer to the next node. The last node’s next is NULL. The examples below share this small header, saved as slist.h:

#ifndef SLIST_H
#define SLIST_H
#include <stdio.h>
#include <stdlib.h>

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

static inline Node *node_create(int data) {
    Node *n = malloc(sizeof *n);
    if (!n) { perror("malloc"); exit(1); }
    n->data = data;
    n->next = NULL;
    return n;
}

static inline void list_print(const Node *head) {
    for (; head; head = head->next) printf("%d -> ", head->data);
    printf("NULL\n");
}

static inline void list_free(Node *head) {
    while (head) {
        Node *next = head->next;   /* save before freeing */
        free(head);
        head = next;
    }
}
#endif

static inline lets every example include the header without “defined but not used” warnings or duplicate-definition link errors. Every program in this lesson was built with -fsanitize=address,undefined, which reports leaks and invalid memory access at runtime. Where a run printed no report, the program was clean.

Building a List

Adding at the front is O(1). Adding at the back means walking to the last node first:

#include "slist.h"

Node *list_prepend(Node *head, int data) {   /* O(1) */
    Node *n = node_create(data);
    n->next = head;
    return n;                                 /* the new head */
}

Node *list_append(Node *head, int data) {    /* O(n): walk to the end */
    Node *n = node_create(data);
    if (!head) return n;
    Node *curr = head;
    while (curr->next) curr = curr->next;
    curr->next = n;
    return head;
}

int main(void) {
    Node *list = NULL;
    for (int i = 1; i <= 3; i++) list = list_append(list, i);
    list_print(list);
    list = list_prepend(list, 0);
    list_print(list);
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o build build.c
$ ./build
1 -> 2 -> 3 -> NULL
0 -> 1 -> 2 -> 3 -> NULL

Both functions return the head, and the caller stores it: list = list_append(list, i). For the first append, the head changes from NULL to the new node, and for every prepend it changes again. Appending n items this way costs O(n²) in total, since each append walks the whole list. Keeping a tail pointer (as the doubly linked list below does) makes it O(1).

Forgetting to Return the New Head

Here is what happens when a function changes only its own copy of the head:

#include "slist.h"

void list_prepend_wrong(Node *head, int data) {
    Node *n = node_create(data);
    n->next = head;
    head = n;                    /* only changes the local copy */
}

int main(void) {
    Node *list = node_create(1);
    list_prepend_wrong(list, 0);
    list_print(list);
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o forgot forgot.c
$ ./forgot
1 -> NULL

=================================================================
==1971==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 16 byte(s) in 1 object(s) allocated from:
    #0 0x7f095ac17a97 in malloc (/usr/local/lib64/libasan.so.8+0xf4a97)
    #1 0x40123a in node_create /w/lists/slist.h:12

The 0 node was created and correctly linked to 1, but main’s list still points at 1, so the new node is unreachable. The list prints as if nothing happened, and LeakSanitizer reports the orphaned 16-byte node (4 bytes of int, 4 of padding, 8 of pointer) at exit. The fix is to return the new head, or to take Node **head and write *head = n.

Deleting a Node

To unlink a node you need its predecessor, because that’s the node whose next changes. Deleting the head is a special case, since it has no predecessor:

#include "slist.h"

Node *list_delete(Node *head, int data) {
    if (!head) return NULL;
    if (head->data == data) {                /* deleting the head itself */
        Node *new_head = head->next;
        free(head);
        return new_head;
    }
    Node *curr = head;                       /* find the node BEFORE the target */
    while (curr->next && curr->next->data != data) curr = curr->next;
    if (curr->next) {
        Node *doomed = curr->next;
        curr->next = doomed->next;           /* unlink, then free */
        free(doomed);
    }
    return head;
}

int main(void) {
    Node *list = NULL;
    for (int i = 5; i >= 1; i--) { Node *n = node_create(i); n->next = list; list = n; }
    list_print(list);
    list = list_delete(list, 3);  list_print(list);
    list = list_delete(list, 1);  list_print(list);
    list = list_delete(list, 9);  list_print(list);
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o delete delete.c
$ ./delete
1 -> 2 -> 3 -> 4 -> 5 -> NULL
1 -> 2 -> 4 -> 5 -> NULL
2 -> 4 -> 5 -> NULL
2 -> 4 -> 5 -> NULL

Deleting 3 rewired 2 -> 4. Deleting 1 took the head branch, and the caller’s list moved to 2. Deleting a missing 9 walked to the end and changed nothing. The order inside the if matters: unlink first, then free. After free(doomed), reading doomed->next would be a use-after-free. Practice 3 shows a Node ** version that removes the special case entirely.

Freeing a List the Wrong Way

list_free saves next before freeing. The “obvious” loop doesn’t:

#include "slist.h"

void list_free_wrong(Node *head) {
    for (Node *n = head; n; n = n->next) {
        free(n);                 /* then n->next reads freed memory */
    }
}

int main(void) {
    Node *a = node_create(1);
    a->next = node_create(2);
    list_free_wrong(a);
    printf("freed\n");
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o badfree badfree.c
badfree.c: In function 'list_free_wrong':
badfree.c:4:31: warning: pointer 'n' used after 'free' [-Wuse-after-free]
    4 |     for (Node *n = head; n; n = n->next) {
      |                             ~~^~~~~~~~~
badfree.c:5:9: note: call to 'free' here
    5 |         free(n);                 /* then n->next reads freed memory */
      |         ^~~~~~~
$ ./badfree
=================================================================
==1842==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000018 at pc 0x000000401568 bp 0x7fff44b8b800 sp 0x7fff44b8b7f8
READ of size 8 at 0x502000000018 thread T0
    #0 0x401567 in list_free_wrong /w/lists/badfree.c:4
    #1 0x401621 in main /w/lists/badfree.c:12
$ gcc -Wall -Wextra -std=c17 -o badfree_plain badfree.c
$ ./badfree_plain
$ echo $?
139

The loop’s update step n = n->next runs after free(n), so it reads the next field of memory that no longer belongs to the program. GCC 14 spots it at compile time, and ASan pinpoints it at runtime (“8 bytes inside of 16-byte region” is exactly the next field). The plain build crashed with a segmentation fault (exit 139) before printing freed, because glibc had already reused those bytes for its own bookkeeping. On another allocator it might have appeared to work.

Reversing and Searching

Reversal walks the list once, pointing each node back at its predecessor. Three pointers are enough:

#include "slist.h"

Node *list_reverse(Node *head) {
    Node *prev = NULL;
    while (head) {
        Node *next = head->next;   /* save the rest of the list */
        head->next = prev;         /* point this node backwards */
        prev = head;
        head = next;
    }
    return prev;                   /* the old tail is the new head */
}

Node *list_find(Node *head, int data) {
    for (; head; head = head->next)
        if (head->data == data) return head;
    return NULL;
}

int main(void) {
    Node *list = NULL;
    for (int i = 4; i >= 1; i--) { Node *n = node_create(i); n->next = list; list = n; }
    list_print(list);
    list = list_reverse(list);
    list_print(list);
    Node *hit = list_find(list, 2);
    printf("find 2: %s, find 7: %s\n", hit ? "found" : "missing",
           list_find(list, 7) ? "found" : "missing");
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o reverse reverse.c
$ ./reverse
1 -> 2 -> 3 -> 4 -> NULL
4 -> 3 -> 2 -> 1 -> NULL
find 2: found, find 7: missing

No node was allocated or freed. Reversal only rewires the links, in O(n) time and O(1) extra space. Saving next before overwriting head->next is the whole trick: skip it and the rest of the list is lost after the first step. Searching is always O(n) with a linked list, because there’s no index to jump to.

Doubly Linked List

Adding a prev pointer, plus a tail pointer in a list header, makes both ends O(1) and lets you remove any node you hold without searching:

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

typedef struct DNode { int data; struct DNode *prev, *next; } DNode;
typedef struct { DNode *head, *tail; size_t size; } DList;

void dlist_push_back(DList *l, int data) {       /* O(1) thanks to tail */
    DNode *n = malloc(sizeof *n);
    if (!n) exit(1);
    *n = (DNode){data, l->tail, NULL};
    if (l->tail) l->tail->next = n; else l->head = n;
    l->tail = n;
    l->size++;
}

void dlist_remove(DList *l, DNode *n) {          /* O(1) given the node */
    if (n->prev) n->prev->next = n->next; else l->head = n->next;
    if (n->next) n->next->prev = n->prev; else l->tail = n->prev;
    free(n);
    l->size--;
}

void dlist_print(const DList *l) {
    for (DNode *n = l->head; n; n = n->next) printf("%d ", n->data);
    printf("| backwards:");
    for (DNode *n = l->tail; n; n = n->prev) printf(" %d", n->data);
    printf(" (size %zu)\n", l->size);
}

int main(void) {
    DList l = {0};
    for (int i = 1; i <= 4; i++) dlist_push_back(&l, i);
    dlist_print(&l);
    dlist_remove(&l, l.head->next);   /* the 2, without searching */
    dlist_remove(&l, l.tail);         /* the 4 */
    dlist_print(&l);
    while (l.head) dlist_remove(&l, l.head);
    dlist_print(&l);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o dlist dlist.c
$ ./dlist
1 2 3 4 | backwards: 4 3 2 1 (size 4)
1 3 | backwards: 3 1 (size 2)
| backwards: (size 0)

Printing both directions is a cheap consistency check: if a prev link were wrong, the backwards walk would disagree with the forwards one. dlist_remove has four cases (middle, head, tail, only node), and the two if/else lines cover all of them. The else branches update the list’s own head and tail when there’s no neighbour to update instead. Draining the list with dlist_remove(&l, l.head) left size 0 and no ASan report, confirming every node was freed.

Circular Lists: The Josephus Problem

In a circular list the last node points back to the first, so traversal never falls off the end. Keeping a pointer to the tail gives O(1) access to both ends, since tail->next is the head:

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

typedef struct CNode { int data; struct CNode *next; } CNode;

/* Append after tail; returns the new tail. tail->next is always the head. */
CNode *circular_insert(CNode *tail, int data) {
    CNode *n = malloc(sizeof *n);
    if (!n) exit(1);
    n->data = data;
    if (!tail) { n->next = n; return n; }   /* one node points to itself */
    n->next = tail->next;
    tail->next = n;
    return n;
}

/* n people in a circle; every k-th person is eliminated */
int josephus(int n, int k) {
    CNode *tail = NULL;
    for (int i = 1; i <= n; i++) tail = circular_insert(tail, i);

    CNode *prev = tail, *curr = tail->next;
    while (curr->next != curr) {
        for (int i = 1; i < k; i++) { prev = curr; curr = curr->next; }
        printf("eliminated %d\n", curr->data);
        prev->next = curr->next;
        free(curr);
        curr = prev->next;
    }
    int survivor = curr->data;
    free(curr);
    return survivor;
}

int main(void) {
    printf("survivor: %d\n", josephus(7, 3));
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o josephus josephus.c
$ ./josephus
eliminated 3
eliminated 6
eliminated 2
eliminated 7
eliminated 5
eliminated 1
survivor: 4

After 7 comes 1, which is why 6 is followed by 2. The count wraps around the circle with no special-case code. The loop ends when a node’s next is itself, meaning one person is left. There’s no NULL in a circular list, so any traversal needs a different stopping rule (usually “back where I started”). The same structure fits round-robin schedulers, which cycle through tasks forever.

Practice

1. Write list_length and list_sum, and check that both handle an empty list.

#include "slist.h"

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

int list_sum(const Node *head) {
    int total = 0;
    for (; head; head = head->next) total += head->data;
    return total;
}

int main(void) {
    Node *list = NULL;
    for (int i = 1; i <= 5; i++) { Node *n = node_create(i * i); n->next = list; list = n; }
    list_print(list);
    printf("length %zu, sum %d\n", list_length(list), list_sum(list));
    printf("empty: length %zu, sum %d\n", list_length(NULL), list_sum(NULL));
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p1 p1.c
$ ./p1
25 -> 16 -> 9 -> 4 -> 1 -> NULL
length 5, sum 55
empty: length 0, sum 0

2. Find the middle node in one pass using a slow pointer (one step) and a fast pointer (two steps).

#include "slist.h"

/* Returns the middle node (the second of two middles for even lengths) */
Node *list_middle(Node *head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

int main(void) {
    for (int len = 1; len <= 4; len++) {
        Node *list = NULL;
        for (int i = len; i >= 1; i--) { Node *n = node_create(i); n->next = list; list = n; }
        printf("length %d: middle = %d\n", len, list_middle(list)->data);
        list_free(list);
    }
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p2 p2.c
$ ./p2
length 1: middle = 1
length 2: middle = 2
length 3: middle = 2
length 4: middle = 3

3. Write list_delete_all(Node **link, int data) that removes every matching node, with no special case for the head.

#include "slist.h"

/* Delete every node holding `data`, using a pointer to the link to update */
void list_delete_all(Node **link, int data) {
    while (*link) {
        if ((*link)->data == data) {
            Node *doomed = *link;
            *link = doomed->next;     /* works for the head and middle alike */
            free(doomed);
        } else {
            link = &(*link)->next;
        }
    }
}

int main(void) {
    int values[] = {2, 2, 5, 2, 7, 2};
    Node *list = NULL;
    for (int i = 5; i >= 0; i--) { Node *n = node_create(values[i]); n->next = list; list = n; }
    list_print(list);
    list_delete_all(&list, 2);
    list_print(list);
    list_free(list);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p3 p3.c
$ ./p3
2 -> 2 -> 5 -> 2 -> 7 -> 2 -> NULL
5 -> 7 -> NULL

4. Write has_cycle using the slow/fast pointers from task 2, and test it on a list whose tail has been linked back to its head.

#include "slist.h"

int has_cycle(const Node *head) {
    const Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

int main(void) {
    Node *a = node_create(1), *b = node_create(2), *c = node_create(3);
    a->next = b; b->next = c;
    printf("straight list: %s\n", has_cycle(a) ? "cycle" : "no cycle");
    c->next = a;                        /* close the loop */
    printf("looped list:   %s\n", has_cycle(a) ? "cycle" : "no cycle");
    c->next = NULL;                     /* break it again before freeing */
    list_free(a);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p4 p4.c
$ ./p4
straight list: no cycle
looped list:   cycle