Hi everyone

In this tutorial we will talk about Forward List

So, What is Forward List actually?

Forward List is a sequence container of C++ STL that stores its elements in a singly linked list. Each element (node) holds its value and a single pointer to the next node — and that is the whole story. There is no pointer going backward, which is exactly what makes forward_list different from list (which is a doubly linked list).

Because every node only knows about the node after it, forward_list can only move in one direction — forward. We cannot walk backward, we cannot jump to the last element cheaply, and there are no reverse iterators.

This sounds like a limitation, and it is — but it is a deliberate one. By dropping the backward pointer, forward_list uses less memory per node than list and is about as lean as a hand-written C-style linked list. It is built for situations where we want a linked list and want to pay for nothing extra.

Forward list’s underlying data structure is a singly linked list. Because of this —

- - - Insertion and deletion are O(1) — as long as we already have an iterator to the position, no shifting of elements is needed (unlike vector)
    - No random access — there is no [ ] or at(), reaching the i-th element takes O(n)
    - Lowest memory overhead of any node-based container — only one pointer per node

💡 Note on availability — Forward list was added in C++11. We need to compile with -std=c++11 or newer.

The one big surprise — no size()

Before we go further, there is one thing about forward_list that catches everyone off guard the first time — it has no size() method.

forward_list is the only standard container that deliberately leaves out size(). The reason is efficiency — keeping a constant-time size() would mean storing and updating an internal counter on every insert and erase, which costs extra memory and slows things down. forward_list is designed to be as lean as a raw linked list, so it skips that.

If we really need the count, we can compute it with std::distance() — but that is an O(n) walk through the whole list —


forward_list <int> numbers = { 10, 20, 30 };

int count = distance(numbers.begin(), numbers.end());
cout << count << endl;

Output will be – 3

Header File Inclusion for forward_list

#include <forward_list>

Declaration & Initialization

Declaring an empty forward list —


forward_list <int> numbers;

The forward list is empty right now.

Declaring a forward list with values —

We can initialize a forward list with values using curly braces —


forward_list <int> numbers = { 10, 20, 30, 40, 50 };

After Initialization numbers will look like this —

Unlike set or flat_set, forward_list keeps the elements in exactly the order we insert them — it does not sort, and it does not remove duplicates.

Declaring a forward list of a given size —

We can declare a forward list of a fixed size, where every element is value-initialized (0 for int) —


// 5 elements, all initialized to 0
forward_list <int> numbers(5);

After this, numbers will look like this —

Declaring a forward list of a given size with a value —

We can also fill every element with a chosen value —


// 5 elements, all initialized to 100
forward_list <int> numbers(5, 100);

After this, numbers will look like this —

100

Declaring forward lists of different types —

Element type can be anything —


forward_list <double> scores;
forward_list <string> nameList;
forward_list <char> letters;
forward_list < pair<int, int> > points;

before_begin() — the iterator before the first element

Here is the second thing that makes forward_list unusual. Since we can only move forward, inserting at the very front is a problem — to insert “before” an element, we need an iterator pointing to the node before it. But the first node has nothing before it.

forward_list solves this with a special iterator called before_begin(). It points to an imaginary position just before the first element. We cannot dereference it (there is no value there), but we can use it as a position for the “after” operations like insert_after and erase_after.


forward_list <int> numbers = { 10, 20, 30 };

// inserting after before_begin() means inserting at the very front
numbers.insert_after(numbers.before_begin(), 5);

// numbers is now { 5, 10, 20, 30 }

💡 Why “after” everything? — In a singly linked list, to insert or delete a node we need to update the next pointer of the previous node. So every editing operation in forward_list works on the position after a given iterator — insert_after, erase_after, emplace_after. before_begin() is what lets these “after” operations reach the very first element.

Insertion

Insertion at the front using push_front()

The cheapest insertion in a forward list is at the front — it is always O(1) —


forward_list <int> numbers;

numbers.push_front(30);
numbers.push_front(20);
numbers.push_front(10);

After insertion, numbers will look like this —

Notice that the elements come out in reverse of how we pushed them — each push_front() puts the new value at the very beginning.

💡 Note — there is no push_back() — Since a singly linked list only knows the next node, jumping to the last node to append would take O(n). So forward_list does not provide push_back() at all. If we need fast insertion at both ends, list (the doubly linked list) is the right tool.

Insertion using emplace_front()

emplace_front() constructs the element in place at the front, avoiding an extra copy —


// numbers is { 10, 20, 30 } before this
numbers.emplace_front(5);

// numbers is now { 5, 10, 20, 30 }

Insertion using insert_after()

insert_after() inserts a value after the position the iterator points to, and returns an iterator to the newly inserted element —


forward_list <int> numbers = { 10, 20, 30 };

auto it = numbers.begin(); // points to 10

// insert 15 after 10
numbers.insert_after(it, 15);

// numbers is now { 10, 15, 20, 30 }

Inserting a value multiple times with insert_after()

We can insert the same value several times by passing a count —


// numbers is { 10, 15, 20, 30 } before this
auto it = numbers.begin(); // points to 10

// insert 99 three times after the first element
numbers.insert_after(it, 3, 99);

// numbers is now { 10, 99, 99, 99, 15, 20, 30 }

Inserting a range with insert_after()

We can also insert a range of values from another container —


forward_list <int> numbers = { 10, 20, 30 };
vector <int> extra = { 7, 8, 9 };

auto it = numbers.begin(); // points to 10
numbers.insert_after(it, extra.begin(), extra.end());

// numbers is now { 10, 7, 8, 9, 20, 30 }

Insertion using emplace_after()

emplace_after() is to insert_after() what emplace_front() is to push_front() — it constructs the element in place after the given position —


forward_list <int> numbers = { 10, 20, 30 };

auto it = numbers.begin(); // points to 10
numbers.emplace_after(it, 25);

// numbers is now { 10, 25, 20, 30 }

Accessing the element

Forward list does not support [ ] or at(), and it has no back() either (reaching the last element would be O(n)). The only direct accessor is front().

front() method

front() returns a reference to the first element —


forward_list <int> numbers = { 10, 20, 30 };

cout << numbers.front() << endl;

Output will be – 10

To reach any other element, we have to walk to it using iterators.

Iterating through a forward list

Range-based for loop

The cleanest way to iterate through a forward list is using a range-based for loop —


for (auto &value : numbers)
{
    cout << value << " ";
}

Output will be – 10 20 30

Using iterator

We can also iterate using iterators directly —


forward_list <int>::iterator it;

for (it = numbers.begin(); it != numbers.end(); it++)
{
    cout << *it << " ";
}

💡 Note on iterators — forward_list only gives us forward iterators. There is no rbegin() or rend(), and we cannot do it--. We can only move forward with it++. This is the direct consequence of being a singly linked list.

Deletion

Deletion at the front using pop_front()

pop_front() removes the first element — an O(1) operation —


forward_list <int> numbers = { 10, 20, 30 };

numbers.pop_front();

// numbers is now { 20, 30 }

There is no pop_back(), for the same reason there is no push_back().

Deletion using erase_after()

erase_after() removes the element after the given position —


forward_list <int> numbers = { 10, 20, 30, 40 };

auto it = numbers.begin(); // points to 10

// erase the element after 10 (which is 20)
numbers.erase_after(it);

// numbers is now { 10, 30, 40 }

To erase the very first element with erase_after(), we use before_begin() —


// numbers is { 10, 30, 40 } before this
// erase the first element
numbers.erase_after(numbers.before_begin());

// numbers is now { 30, 40 }

Deletion of a range using erase_after()

erase_after() also has a range version. It removes everything between two iterators — exclusive on both ends —


forward_list <int> numbers = { 10, 20, 30, 40, 50 };

auto first = numbers.begin();          // points to 10
auto last = next(first, 3);            // points to 40

// removes 20 and 30 (everything strictly between first and last)
numbers.erase_after(first, last);

// numbers is now { 10, 40, 50 }

remove() method

remove() deletes all elements equal to a given value —


forward_list <int> numbers = { 10, 20, 10, 30, 10 };

numbers.remove(10);

// numbers is now { 20, 30 }

remove_if() method

remove_if() deletes all elements that satisfy a predicate —


// remove all elements greater than 25
numbers.remove_if([](int value) {
    return value > 25;
});

clear() method

If we want to remove all elements of the forward list, we can use clear() —


numbers.clear();

After clear(), numbers will be empty.

forward_list operations

Just like list, forward_list comes with a set of built-in member functions for operations that would be clumsy to do from the outside. These are specially designed to take advantage of the linked-list structure.

splice_after() method

splice_after() moves elements from one forward list into another, after a given position — without copying any nodes. The source loses the elements, the destination gains them —


forward_list <int> listOne = { 1, 2, 3 };
forward_list <int> listTwo = { 100, 200 };

// move all of listTwo into listOne, after the first element
listOne.splice_after(listOne.begin(), listTwo);

// listOne is now { 1, 100, 200, 2, 3 }
// listTwo is now empty

💡 Why splice_after() is special — It just re-points a few next pointers. No element is copied or moved in memory, so splicing even a huge list is O(1) (for the single-element version) or linear only in the number of spliced nodes. This is something vector simply cannot do.

unique() method

unique() removes consecutive duplicate elements. To remove all duplicates, we sort first —


forward_list <int> numbers = { 10, 10, 20, 30, 30, 30, 10 };

numbers.unique();

// numbers is now { 10, 20, 30, 10 }
// note the last 10 stays — it was not adjacent to the others

merge() method

merge() merges two sorted forward lists into one sorted forward list. The source becomes empty afterwards —


forward_list <int> listOne = { 10, 30, 50 };
forward_list <int> listTwo = { 20, 40, 60 };

listOne.merge(listTwo);

// listOne is now { 10, 20, 30, 40, 50, 60 }
// listTwo is now empty

sort() method

We cannot use std::sort() on a forward list, because std::sort() needs random-access iterators. So forward_list provides its own sort() member —


forward_list <int> numbers = { 30, 10, 50, 20, 40 };

numbers.sort();

// numbers is now { 10, 20, 30, 40, 50 }

We can also pass a comparator to sort in descending order —


numbers.sort(greater<int>());

// numbers is now { 50, 40, 30, 20, 10 }

reverse() method

reverse() flips the order of the elements —


forward_list <int> numbers = { 10, 20, 30 };

numbers.reverse();

// numbers is now { 30, 20, 10 }

resize() and empty()

resize() method

resize() changes the number of elements. If we grow the list, the new elements are value-initialized (or filled with a value we pass) —


forward_list <int> numbers = { 10, 20, 30 };

numbers.resize(5);       // { 10, 20, 30, 0, 0 }
numbers.resize(2);       // { 10, 20 }
numbers.resize(4, 99);   // { 10, 20, 99, 99 }

empty() method

empty() returns true if the forward list has no elements. Since there is no size(), this is the standard way to check for an empty list —


if (numbers.empty())
{
    cout << "Forward list is empty" << endl;
}

Swapping

swap() method

STL forward list has a method named swap(), which swaps all the elements between two forward lists —


forward_list <int> listOne = { 1, 2, 3 };
forward_list <int> listTwo = { 10, 20, 30, 40, 50 };

// swapping values between two forward lists
listOne.swap(listTwo);

After swapping, listOne will have the elements of listTwo, and listTwo will have the elements of listOne. Because swap() only exchanges the internal head pointers, it is an O(1) operation.

Forward List vs List vs Vector

This is the biggest question when picking between these three — so it is worth laying them side by side.

Property	forward_list	list	vector
Underlying data structure	Singly linked list	Doubly linked list	Dynamic array
Random access ([ ] / at())	No	No	Yes, O(1)
Direction of traversal	Forward only	Both directions	Both directions
Insert / erase at a known position	O(1)	O(1)	O(n)
push_front() / pop_front()	O(1)	O(1)	O(n)
push_back() / back()	Not available	O(1)	O(1)
size()	Not available (use distance)	O(1)	O(1)
Memory per element	Lowest (one pointer)	Higher (two pointers)	Lowest (no pointers, but may over-allocate)
Cache friendliness	Poor (scattered nodes)	Poor (scattered nodes)	Excellent (contiguous)
C++ version	C++11	C++98	C++98
Use when	We need a lean forward-only list with O(1) front edits	We need two-way traversal and edits at both ends	We need random access and cache-friendly storage

Time Complexity

Operation	Description	Time Complexity
push_front()	Insert an element at the front	O(1)
emplace_front()	Construct and insert at the front	O(1)
pop_front()	Remove the front element	O(1)
insert_after()	Insert after a position	O(1) per element
emplace_after()	Construct and insert after a position	O(1)
erase_after()	Remove the element(s) after a position	O(1) single, O(k) range
front()	Access the first element	O(1)
before_begin()	Iterator just before the first element	O(1)
begin() / end()	Iterators to the beginning and end	O(1)
remove()	Remove all elements equal to a value	O(n)
remove_if()	Remove all elements matching a predicate	O(n)
unique()	Remove consecutive duplicates	O(n)
merge()	Merge two sorted forward lists	O(n)
splice_after()	Move elements from another forward list	O(1) single, O(k) range
sort()	Sort the elements	O(n log n)
reverse()	Reverse the order of elements	O(n)
resize()	Change the number of elements	O(n)
empty()	Returns true if forward list is empty	O(1)
clear()	Removes all elements	O(n)
swap()	Swaps contents of two forward lists	O(1)
distance(begin, end)	Counts the elements (no size() member)	O(n)

Applications

- - - Implementing memory-efficient linked lists where the backward pointer of a doubly linked list would be wasted
    - Hash table buckets using separate chaining — each bucket is a small singly linked list
    - Adjacency lists for graphs where we only ever traverse neighbors forward
    - Free lists in custom memory allocators, where nodes are pushed and popped from the front
    - Undo/redo style stacks where only front insertion and removal are needed
    - Any place a hand-written singly linked list would be used, but with the safety and convenience of the STL
    - Splicing nodes between lists cheaply (O(1)) without invalidating iterators, using splice_after()
    - Embedded and memory-constrained systems where every byte per node counts

In the next tutorial we will talk about another useful STL container.

Until then
Happy Coding