What is std::forward_list — Singly Linked List in C++?

C++ std::forward_list for singly-linked storage with O(1) front insertion, minimal memory per node, forward-only iteration, and when to use it over std::list.

Which C++ standard introduced std::forward_list — Singly Linked List?

std::forward_list — Singly Linked List was introduced in C++11.

What is the difficulty level of std::forward_list — Singly Linked List?

std::forward_list — Singly Linked List is considered Intermediate-level C++ material.

std::forward_list — Singly Linked List

std::forward_listsince C++11

A singly-linked list container with O(1) front insertion and one pointer per node, offering minimal per-element memory overhead at the cost of forward-only traversal and no random access.

Overview

std::forward_list<T> was introduced in C++11 to provide a standards-compliant singly-linked list. It trades bidirectional traversal for memory efficiency: each node stores only one pointer to the next element, unlike std::list which stores two (next and previous). This design delivers zero time and space overhead relative to a hand-written C-style singly linked list.

Singly-linked lists excel in scenarios requiring frequent front insertion or when you only iterate forward through the sequence once. However, they impose a harsh constraint: you cannot efficiently access the element before a position. This manifests in a unique API: operations like insert() and erase() become insert_after() and erase_after().

The container deliberately omits size(). Computing size on a singly-linked list requires traversing all elements (O(n)), so the standard chose not to cache it, enforcing conscious design decisions about when you need the count.

Syntax

cpp

Godbolt

#include <forward_list>

// Construction (C++11)
std::forward_list<int> fl;                    // empty
std::forward_list<int> fl = {1, 2, 3};        // brace initialization
std::forward_list<int> fl(other);             // copy
std::forward_list<int> fl(std::move(other));  // move

Key member functions:

cpp

Godbolt

// Front access (only)
fl.push_front(val);        // O(1)
fl.emplace_front(args...); // O(1), in-place construction
fl.pop_front();            // O(1)
fl.front();                // O(1), returns T&

// No back(), no size(), no operator[], no rbegin/rend

// Iteration (forward only)
fl.begin(); fl.end();      // forward iterators
fl.cbegin(); fl.cend();    // const forward iterators
fl.before_begin();         // virtual iterator before first element

// Insertion/erasure (after an iterator)
fl.insert_after(pos, val);              // O(1), insert after pos
fl.insert_after(pos, count, val);       // O(1) insertion time
fl.insert_after(pos, first, last);      // O(1) insertion time
fl.emplace_after(pos, args...);         // O(1), in-place
fl.erase_after(pos);                    // O(1)
fl.erase_after(pos, last);              // O(1)

// Splice (move elements, zero-copy)
fl.splice_after(pos, other);            // move all of other after pos
fl.splice_after(pos, other, it);        // move *it after pos
fl.splice_after(pos, other, first, last); // move range after pos

// Sorting and merging
fl.sort();                              // O(n log n), in-place
fl.merge(other);                        // merge two sorted lists, O(n)
fl.unique();                            // remove consecutive duplicates, O(n)
fl.reverse();                           // O(n)

Examples

Basic Front Operations

cpp

Godbolt

#include <forward_list>
#include <print>

std::forward_list<int> fl = {2, 3, 4};

// Fast front insertion
fl.push_front(1);
fl.emplace_front(0);  // constructs 0 in-place
// fl = {0, 1, 2, 3, 4}

// Fast front removal
fl.pop_front();
// fl = {1, 2, 3, 4}

std::println("front: {}", fl.front());  // 1

Insertion After (The Singly-Linked Twist)

cpp

Godbolt

std::forward_list<int> fl = {1, 2, 4, 5};

auto it = fl.begin();
++it;  // now points to 2

// Insert 3 after position pointing to 2
fl.insert_after(it, 3);
// fl = {1, 2, 3, 4, 5}

// Insert range after position
fl.insert_after(it, {10, 11});
// fl = {1, 2, 10, 11, 3, 4, 5}

// Erase element immediately after iterator
fl.erase_after(it);
// fl = {1, 2, 11, 3, 4, 5}

before_begin() for Front Manipulation

cpp

Godbolt

std::forward_list<int> fl = {2, 3, 4};

// before_begin() is a virtual iterator to the position before the first element
// Use it to insert or erase at the front via insert_after/erase_after

fl.insert_after(fl.before_begin(), 1);  // prepend 1
// fl = {1, 2, 3, 4}

fl.erase_after(fl.before_begin());       // remove front
// fl = {2, 3, 4}

Sorting and Merging Sorted Lists

cpp

Godbolt

std::forward_list<int> a = {3, 1, 4, 1, 5, 9};
std::forward_list<int> b = {2, 6, 5, 3};

a.sort();     // {1, 1, 3, 4, 5, 9}
b.sort();     // {2, 3, 5, 6}

a.merge(b);   // merge sorted lists into a; b becomes empty
// a = {1, 1, 2, 3, 3, 4, 5, 5, 6, 9}

// Remove consecutive duplicates (requires sorted list)
a.unique();
// a = {1, 2, 3, 4, 5, 6, 9}

Zero-Copy Splice

cpp

Godbolt

std::forward_list<int> src = {10, 20, 30};
std::forward_list<int> dst = {1, 2, 3};

auto pos = dst.begin();
++pos;  // position at 2

// Move all elements of src after position in dst (zero-copy)
dst.splice_after(pos, src);
// dst = {1, 2, 10, 20, 30, 3}
// src = {} (empty, no elements copied)

Best Practices

Use only when singly-linked semantics matter: If you never need size(), never traverse backward, and heavily manipulate the front, forward_list saves one pointer per node. This is rarely enough to justify the restricted API in practice.
Avoid computing size(): Since there is no size() member, each size computation requires O(n) traversal. Cache it yourself if needed, or redesign to avoid asking "how many?"
Prefer emplace_front() for construction: Both push_front() and emplace_front() are O(1), but emplace_front(args...) constructs the element in-place without temporaries.
Use splice_after() for bulk moves: When transferring sequences of elements between lists, splice_after() is zero-copy and vastly faster than erase-and-insert loops.
Remember insert_after and erase_after: The API intentionally lacks insert(pos, val) and erase(pos). Always use *_after variants to clarify singly-linked semantics and avoid subtle bugs.
Iterate once: Singly-linked lists suit one-pass algorithms. If you iterate multiple times or need random access, std::vector or std::deque will be faster.

Common Pitfalls

Forgetting before_begin(): Prepending or removing the front element can be done with push_front() or pop_front(), but generic manipulation at the front requires insert_after(before_begin(), ...) and erase_after(before_begin(), ...).
Assuming you can traverse backward: Iterators are forward-only; --it is illegal. No rbegin(), no rend(). If you need bidirectional traversal, use std::list.
Calling size() when it doesn't exist: There is no size() method. Each call would require a full traversal: O(n). Use empty() (O(1)) when possible, or cache the count yourself.
Expecting random access: operator[] and direct subscripting do not exist. Use std::next(it, k) to reach the kth element (still O(k)).
Splicing within the same list carelessly: Splicing elements within the same list can easily create logic errors or create cycles. Ensure the source and destination positions don't overlap unintentionally.

Performance Comparison

Characteristic	`forward_list`	`std::list`	`std::vector`
Memory/node	1 pointer	2 pointers	0 (contiguous block)
Front insert	O(1)	O(1)	O(n)
Arbitrary insert	O(1) (with iterator)	O(1) (with iterator)	O(n)
Random access	✗	✗	O(1)
Iteration	Forward only	Bidirectional	Random access
Cache locality	Poor	Poor	Excellent
size()	✗ (O(n) if computed)	O(1)	O(1)

Choose forward_list only when the single-pointer-per-node savings justify the restricted API. In most cases, std::vector offers better cache locality and simpler iteration; std::list offers bidirectional traversal at the cost of one extra pointer per node.