Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# 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) |
| Access by index | O(n) |
| Append to tail | O(n) |
| Search | O(n) |