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 doubly linked list, and simpler to implement and reason about.

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.

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.

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;
};

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.

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

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.

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);
}

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.

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;
    }
}

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

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;
    }
}

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.

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;
    }
}

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.

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);
}

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

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;
}

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.

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;
}

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.

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;
}

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.

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;
}