# Forward list
A **forward list** is a singly linked list with a single pointer to the head and no tail pointer. Each node holds a value and a `next` pointer; there is no `prev`. Traversal is one-directional: from head toward NULL. It is the minimal linked sequence — less memory per node than a [[linked-list|doubly linked list]], and simpler to implement and reason about.

```c
struct node {
    int         val;
    struct node *next;
};
```

The absence of a tail pointer means appending to the end costs O(n), because you must traverse to the last node first. This makes the forward list most practical when insertions happen at or near the head, or when the full list is built up-front and then only read sequentially. Stacks, free lists in memory allocators, and intrusive linked lists in kernel data structures are common uses.

Deleting a node requires a pointer to its predecessor, not to the node itself, because the predecessor's `next` must be updated. This is an ergonomic quirk compared to doubly linked lists, where deletion from a known pointer is truly O(1) without needing the predecessor.

| Operation | Time |
|---|---|
| Insert/delete at head | O(1) |
| Insert after a given node | O(1) |
| Remove after a given node | O(1) |
| Access by index | O(n) |
| Append to tail | O(n) |
| Search | O(n) |
| Reverse | O(n) |

## Structure
A generic forward list separates the node type from the payload type by storing an opaque `void*` in each node, rather than embedding a fixed value type directly. The list itself is just a pointer to the head node; a `list_t` wrapper adds a tail pointer purely as an O(1) append optimization for this implementation, even though a minimal forward list does not strictly need one. Traversal still only moves forward through `ln_next`, and there is still no `ln_prev`.

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \foreach \i/\x in {1/0,2/1.6,3/3.2,4/4.8} {
    \node[node] (n\i) at (\x,0) {\i};
  }
  \foreach \i/\j in {1/2,2/3,3/4} {
    \draw[thick,->] (n\i.east) -- (n\j.west);
  }
  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};
\end{tikzpicture}
\end{document}

```c
typedef struct list_node list_node_t;
typedef struct list list_t;
struct list_node {
    void        *ln_data;
    list_node_t *ln_next;    
};
struct list {
    list_node_t *ln_head;
    list_node_t *ln_tail;
};
```

## Operations

### Create
The list starts as a zeroed `list_t`: `ln_head` and `ln_tail` both NULL. `calloc()` is a convenient way to get this for free when the list itself is heap-allocated.

```c
list_t *list_create(void) {
    return calloc(1, sizeof(list_t));
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[>={Stealth[round]}]
  \node (head) at (0,0) {head};
  \node (tail) at (2.4,0) {tail};
  \node[draw,thick,rectangle,minimum width=1.1cm,minimum height=0.6cm] (null) at (1.2,-1.3) {NULL};
  \draw[thick,->] (head.south) -- (null.north west);
  \draw[thick,->] (tail.south) -- (null.north east);
\end{tikzpicture}
\end{document}

### Destroy
Freeing the list means walking from `ln_head` to NULL, freeing each node, then freeing the list struct itself. The payload pointed to by `ln_data` is the caller's responsibility unless the list owns it.

```c
void list_destroy(list_t *list) {
    list_node_t *cur = list->ln_head;
    while (cur != NULL) {
        list_node_t *next = cur->ln_next;
        free(cur);
        cur = next;
    }
    free(list);
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node] (n3) at (3.2,0) {3};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[thick,->] (n2.east) -- (n3.west);
  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL};

  \node[node,draw=gray,dashed,text=gray] (m1) at (0,-2) {1};
  \node[node,draw=gray,dashed,text=gray] (m2) at (1.6,-2) {2};
  \node[node,draw=gray,dashed,text=gray] (m3) at (3.2,-2) {3};
  \foreach \n in {m1,m2,m3} {
    \draw[gray,thick] (\n.south west) -- (\n.north east);
    \draw[gray,thick] (\n.north west) -- (\n.south east);
  }
  \node[gray] at (1.6,-2.9) {free()'d, list = NULL};
\end{tikzpicture}
\end{document}

### Append
Because `ln_tail` is tracked, appending is O(1): the new node is linked after the current tail, and `ln_tail` is advanced. Without a tail pointer this would require an O(n) traversal, as noted above.

```c
void list_append(list_t *list, void *data) {
    list_node_t *node = malloc(sizeof(list_node_t));
    node->ln_data = data;
    node->ln_next = NULL;
    if (list->ln_tail == NULL) {
        list->ln_head = list->ln_tail = node;
    } else {
        list->ln_tail->ln_next = node;
        list->ln_tail = node;
    }
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node] (n3) at (3.2,0) {3};
  \node[node,draw=teal,thick,fill=teal!15] (n4) at (4.8,0) {4};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[thick,->] (n2.east) -- (n3.west);
  \draw[teal,thick,->] (n3.east) -- (n4.west);
  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};
  \node at (3.2,0.9) {tail (before)};
  \draw[thick,->,dashed] (3.2,0.65) -- (3.2,0.45);
  \node[teal] at (4.8,0.9) {tail (after)};
  \draw[teal,thick,->,dashed] (4.8,0.65) -- (4.8,0.45);
\end{tikzpicture}
\end{document}

### Prepend
Prepending is O(1) regardless of whether a tail pointer exists, since it only ever touches the head.

```c
void list_prepend(list_t *list, void *data) {
    list_node_t *node = malloc(sizeof(list_node_t));
    node->ln_data = data;
    node->ln_next = list->ln_head;
    list->ln_head = node;
    if (list->ln_tail == NULL) {
        list->ln_tail = node;
    }
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node,draw=teal,thick,fill=teal!15] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node] (n3) at (3.2,0) {3};
  \draw[teal,thick,->] (n1.east) -- (n2.west);
  \draw[thick,->] (n2.east) -- (n3.west);
  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL};
  \node[teal] at (0,0.9) {head (after)};
  \draw[teal,thick,->,dashed] (0,0.65) -- (0,0.45);
  \node at (1.6,0.9) {head (before)};
  \draw[thick,->,dashed] (1.6,0.65) -- (1.6,0.45);
\end{tikzpicture}
\end{document}

### Insert after
Inserting after a given node is O(1) because it only touches two links: the new node's `ln_next` and the given node's `ln_next`. This is the operation a forward list is actually good at, and the reason algorithms hold onto a node pointer rather than an index when they can. If the given node happens to be the tail, `ln_tail` must be advanced too.

```c
void list_insert_after(list_t *list, list_node_t *node, void *data) {
    list_node_t *n = malloc(sizeof(list_node_t));
    n->ln_data = data;
    n->ln_next = node->ln_next;
    node->ln_next = n;
    if (list->ln_tail == node) {
        list->ln_tail = n;
    }
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node] (n3) at (3.2,0) {3};
  \node[node,draw=teal,thick,fill=teal!15] (nx) at (1.6,-1.6) {X};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[gray,thick,dashed] (n2.east) to[bend left=15] (n3.west);
  \draw[teal,thick,->] (n2.south) -- (nx.north west);
  \draw[teal,thick,->] (nx.north east) -- (n3.south);
  \draw[thick,->] (n3.east) -- ++(1.2,0) node[right] {NULL};
\end{tikzpicture}
\end{document}

### Remove after
The mirror of insert-after: freeing the node that follows a given one only touches links on either side of the doomed node, so it is O(1). This is why deleting a known node in a forward list needs a pointer to its *predecessor* rather than to the node itself, as noted above; remove-after is the operation that predecessor pointer is for.

```c
void list_remove_after(list_t *list, list_node_t *node) {
    list_node_t *doomed = node->ln_next;
    if (doomed == NULL) return;
    node->ln_next = doomed->ln_next;
    if (list->ln_tail == doomed) {
        list->ln_tail = node;
    }
    free(doomed);
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node,draw=gray,dashed,text=gray] (n3) at (3.2,0) {3};
  \node[node] (n4) at (4.8,0) {4};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[gray,thick] (n3.south west) -- (n3.north east);
  \draw[gray,thick] (n3.north west) -- (n3.south east);
  \draw[thick,->] (n2.east) to[bend left=25] (n4.west);
  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};
  \node[gray] at (3.2,-0.9) {free()'d};
\end{tikzpicture}
\end{document}

### Search
A linear scan comparing `ln_data` against a target using a caller-supplied comparator, since the list is generic over the payload type.

```c
list_node_t *list_search(list_t *list, void *key, int (*cmp)(void *, void *)) {
    list_node_t *cur = list->ln_head;
    while (cur != NULL) {
        if (cmp(cur->ln_data, key) == 0) return cur;
        cur = cur->ln_next;
    }
    return NULL;
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {7};
  \node[node] (n2) at (1.6,0) {3};
  \node[node,draw=orange,thick,fill=orange!15] (n3) at (3.2,0) {9};
  \node[node] (n4) at (4.8,0) {2};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[thick,->] (n2.east) -- (n3.west);
  \draw[thick,->] (n3.east) -- (n4.west);
  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};
  \node[orange] at (3.2,-0.9) {key = 9, found};
\end{tikzpicture}
\end{document}

### Length
Since there is no size field, computing the length costs an O(n) traversal. A forward list that needs frequent length queries should cache a count in `list_t` and maintain it in every insert/remove, trading a little bookkeeping for O(1) lookups.

```c
size_t list_length(list_t *list) {
    size_t n = 0;
    for (list_node_t *cur = list->ln_head; cur != NULL; cur = cur->ln_next) {
        n++;
    }
    return n;
}
```

### Reverse
Reversal is done in place with the classic three-pointer walk: `prev`, `cur`, and a saved `next` so the forward link isn't lost the moment it's overwritten. Each node's `ln_next` is flipped to point backward, and `prev` and `cur` both advance one step. The old head ends up as the new tail and vice versa, so both `ln_head` and `ln_tail` need updating.

```c
void list_reverse(list_t *list) {
    list_node_t *prev = NULL;
    list_node_t *cur = list->ln_head;
    list->ln_tail = cur;
    while (cur != NULL) {
        list_node_t *next = cur->ln_next;
        cur->ln_next = prev;
        prev = cur;
        cur = next;
    }
    list->ln_head = prev;
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (n1) at (0,0) {1};
  \node[node] (n2) at (1.6,0) {2};
  \node[node] (n3) at (3.2,0) {3};
  \node[node] (n4) at (4.8,0) {4};
  \draw[thick,->] (n1.east) -- (n2.west);
  \draw[thick,->] (n2.east) -- (n3.west);
  \draw[thick,->] (n3.east) -- (n4.west);
  \draw[thick,->] (n4.east) -- ++(1.2,0) node[right] {NULL};

  \node[node,draw=teal,fill=teal!10] (m1) at (0,-2) {1};
  \node[node,draw=teal,fill=teal!10] (m2) at (1.6,-2) {2};
  \node[node,draw=teal,fill=teal!10] (m3) at (3.2,-2) {3};
  \node[node,draw=teal,fill=teal!10] (m4) at (4.8,-2) {4};
  \draw[teal,thick,<-] (m1.east) -- (m2.west);
  \draw[teal,thick,<-] (m2.east) -- (m3.west);
  \draw[teal,thick,<-] (m3.east) -- (m4.west);
  \draw[teal,thick,->] (m1.west) -- ++(-1.2,0) node[left] {NULL};
\end{tikzpicture}
\end{document}

### Sort
In-place sorting a singly linked list is naturally suited to merge sort: splitting the list in half only requires forward pointers (advance a slow and a fast pointer to find the midpoint), and merging two sorted forward lists only requires relinking `ln_next` pointers, no random access. Quicksort's partitioning step, by contrast, wants two-directional swaps, which the forward list cannot do efficiently.

```c
static list_node_t *split(list_node_t *head) {
    list_node_t *slow = head, *fast = head->ln_next;
    while (fast != NULL && fast->ln_next != NULL) {
        slow = slow->ln_next;
        fast = fast->ln_next->ln_next;
    }
    list_node_t *mid = slow->ln_next;
    slow->ln_next = NULL;
    return mid;
}

static list_node_t *merge(list_node_t *a, list_node_t *b, int (*cmp)(void *, void *)) {
    list_node_t head = {0};
    list_node_t *tail = &head;
    while (a != NULL && b != NULL) {
        if (cmp(a->ln_data, b->ln_data) <= 0) {
            tail->ln_next = a;
            a = a->ln_next;
        } else {
            tail->ln_next = b;
            b = b->ln_next;
        }
        tail = tail->ln_next;
    }
    tail->ln_next = (a != NULL) ? a : b;
    return head.ln_next;
}

static list_node_t *merge_sort(list_node_t *head, int (*cmp)(void *, void *)) {
    if (head == NULL || head->ln_next == NULL) return head;
    list_node_t *mid = split(head);
    return merge(merge_sort(head, cmp), merge_sort(mid, cmp), cmp);
}

void list_sort(list_t *list, int (*cmp)(void *, void *)) {
    list->ln_head = merge_sort(list->ln_head, cmp);
    list_node_t *cur = list->ln_head;
    while (cur != NULL && cur->ln_next != NULL) {
        cur = cur->ln_next;
    }
    list->ln_tail = cur;
}
```

\documentclass[border=5pt]{standalone}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\begin{document}
\begin{tikzpicture}[node/.style={draw,thick,circle,minimum width=0.8cm,minimum height=0.8cm},>={Stealth[round]}]
  \node[node] (b1) at (0,0) {3};
  \node[node] (b2) at (1.6,0) {1};
  \node[node] (b3) at (3.2,0) {4};
  \node[node] (b4) at (4.8,0) {2};
  \draw[thick,->] (b1.east) -- (b2.west);
  \draw[thick,->] (b2.east) -- (b3.west);
  \draw[thick,->] (b3.east) -- (b4.west);
  \draw[thick,->] (b4.east) -- ++(1.2,0) node[right] {NULL};
  \node at (-1.1,0) {before};

  \node[node,draw=teal,fill=teal!10] (a1) at (0,-2) {1};
  \node[node,draw=teal,fill=teal!10] (a2) at (1.6,-2) {2};
  \node[node,draw=teal,fill=teal!10] (a3) at (3.2,-2) {3};
  \node[node,draw=teal,fill=teal!10] (a4) at (4.8,-2) {4};
  \draw[teal,thick,->] (a1.east) -- (a2.west);
  \draw[teal,thick,->] (a2.east) -- (a3.west);
  \draw[teal,thick,->] (a3.east) -- (a4.west);
  \draw[teal,thick,->] (a4.east) -- ++(1.2,0) node[right] {NULL};
  \node at (-1.1,-2) {after};
\end{tikzpicture}
\end{document}