Table of Contents
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 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.
| 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) |
