C++ STL

list / forward_list

Complete lesson for list / forward_list using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — list / forward_list

Section: C++ STL. C++ linked lists — std::list and std::forward_list: insert/erase, splice, and Vector vs List.

What is a list?

std::list is a **doubly linked list** — each node points to previous and next.
std::forward_list is a **singly linked list** — each node points only forward.
Both are **node-based**: no operator[], no random access in O(1).
Insert/erase are **O(1) once you have an iterator** to the spot.
Headers: #include and #include
**Real-life:** a playlist or train cars — easy to unhook/relink in the middle.

Idea	Meaning
Node-based	Elements live in separate nodes + pointers
No `[]`	Walk with iterators — access by index is O(n)
Stable iterators	Other nodes stay valid when you erase one
Default choice?	Usually no — prefer `vector` first

Why use list / forward_list?

Many inserts/erases in the **middle** when you already hold iterators.
splice can move whole ranges between lists without copying elements.
Iterator stability matters more than cache locality for your workload.
Otherwise prefer **vector** (or deque for both-end ops).

Benefit	What you gain
O(1) mid insert (with iterator)	No shifting of other elements
splice	Move nodes between lists cheaply
Iterator stability	Erase one node; others remain valid
forward_list lightness	One pointer per node

Differences between Vector and List

Classic interview table — pick the container that matches your access pattern.

Feature	Vector (`std::vector`)	List (`std::list`)
Structure	Contiguous dynamic array	Doubly linked nodes
Random access `[]`	O(1)	Not supported (O(n) walk)
`push_back`	Amortized O(1)	O(1)
`push_front`	O(n)	O(1)
Insert/erase middle	O(n) — shifts elements	O(1) given iterator
Find by value / index	Index O(1); find O(n)	Always O(n) to locate
Cache locality	Excellent	Poor (pointer chasing)
Memory overhead	One buffer + unused capacity	Two pointers per node
Iterator invalidation	Realloc / mid erase invalidates many	Only erased node iterators
`splice` / relink	N/A (copy/move elements)	O(1) node relinking
Sorting	`std::sort` works	Use member `list::sort`
Default recommendation	Yes — most cases	Only for special mid-node workloads
Header

Differences between list and forward_list

Same linked-list idea; different link direction and API.

Feature	`list`	`forward_list`
Links	Doubly linked	Singly linked
Traversal	Forward + backward	Forward only
`push_back`	Yes	No
`push_front`	Yes	Yes
Insert API	`insert(it, x)` before `it`	`insert_after(it, x)` after `it`
Erase API	`erase(it)`	`erase_after(it)`
`size()`	O(1)	O(n)
Memory per node	Prev + next pointers	Next pointer only
`before_begin()`	No	Yes — for front insert_after
`splice`	Yes	`splice_after`
Header

list — doubly linked operations

push_front / push_back, pop_front / pop_back.
insert(pos, value), erase(pos), remove(value), remove_if.
unique, reverse, sort (member), merge, splice.
Bidirectional iterators + reverse iterators.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> L = {1, 2, 3};
    L.push_front(0);
    L.push_back(4);
    L.insert(next(L.begin(), 2), 99);
    L.remove(2);
    for (int x : L) cout << x << " ";
    cout << "\n";
    return 0;
}

forward_list — singly linked operations

Only forward iterators — no --it.
push_front, insert_after, erase_after, remove, reverse, sort.
before_begin() points before the first element (not dereferenceable).
Use when you want a lighter list and only walk forward.

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {2, 3};
    fl.push_front(1);
    fl.insert_after(fl.before_begin(), 0);
    auto it = fl.begin();
    fl.insert_after(it, 5);
    for (int x : fl) cout << x << " ";
    cout << "\n";
    return 0;
}

Creating and traversing

Initializer lists, fill constructors, and range-for work like other containers.
To reach the i-th element you must advance an iterator (O(n)).

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
    list<int> L = {10, 20, 30, 40};
    auto it = L.begin();
    advance(it, 2);
    cout << *it << "\n";
    for (auto r = L.rbegin(); r != L.rend(); ++r)
        cout << *r << " ";
    cout << "\n";
    return 0;
}

When to use which

Most sequences → **vector**.
Both-end ops + indexing → **deque**.
Heavy mid insert with held iterators / splice → **list**.
Light forward-only chain → **forward_list**.

Need	Prefer
Random access / cache-friendly	`vector`
Front + back + index	`deque`
Stable mid erase + splice	`list`
Minimal node memory, forward only	`forward_list`

Key points to remember

No operator[] on list/forward_list.
list bidirectional; forward_list forward + *_after APIs.
Insert/erase O(1) **at iterator**; finding the iterator is O(n).
Prefer vector unless you measured a list win.
forward_list::size() is O(n).

Advanced — list / forward_list

Complexity cheat sheet

Costs assume you already have the right iterator where needed.

Operation	`list`	`forward_list`
Access by index	O(n)	O(n)
`push_front`	O(1)	O(1)
`push_back`	O(1)	—
Insert/erase at iterator	O(1)	O(1) after position
`size()`	O(1)	O(n)
Traverse all	O(n)	O(n)
`splice` / `splice_after`	Often O(1) node moves	After-position APIs

splice on list

splice transfers nodes from one list to another **without copying** elements.
Great for rearrange-heavy pipelines and merging queues of nodes.

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> a = {1, 2};
    list<int> b = {3, 4};
    a.splice(a.end(), b);
    for (int x : a) cout << x << " ";
    cout << "\n";
    return 0;
}

Iterator invalidation

Erasing a node invalidates **only** iterators/references to that node.
Insert does not invalidate other iterators.
This is a major difference from vector reallocation rules.

list::sort vs std::sort

std::sort needs random-access iterators — **not** for list.
Use the member L.sort() instead.
forward_list also has a member sort().

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> L = {4, 1, 3, 2};
    L.sort();
    for (int x : L) cout << x << " ";
    cout << "\n";
    return 0;
}

remove, unique, merge

remove(value) erases all matching elements.
unique() erases consecutive duplicates (sort first for global uniqueness).
merge combines two **sorted** lists.

Design tips

Default to vector; switch to list only with a profiled reason.
If you need index i often, list is the wrong tool.
Hold iterators across inserts carefully — only erased positions die.
For FIFO only, prefer queue / deque over rolling your own list.

Tricky Interview Points

Q1) What is std::list?

Answer A doubly linked list STL container with bidirectional iterators and O(1) insert/erase at a known position.

Q2) list vs forward_list?

Answer list is doubly linked (bidirectional, push_back); forward_list is singly linked (forward only, lighter, insert_after).

Q3) Vector vs list — main differences?

Answer Vector is contiguous with O(1) index access; list is node-based with O(1) mid insert given an iterator but no [].

Q4) Does list support operator[]?

Answer No. You advance iterators; random access is O(n).

Q5) Why prefer vector over list usually?

Answer Better cache locality, O(1) indexing, and simpler performance for most workloads.

Q6) What is splice?

Answer A list operation that moves nodes between lists (or within a list) without copying element values.

Q7) How do you sort a list?

Answer Call the member list::sort(); std::sort will not work because list iterators are not random-access.

Q8) Iterator invalidation on erase?

Answer Only iterators to the erased element are invalidated; others remain valid.

Q9) How to insert at the front of a forward_list?

Answer push_front, or insert_after(before_begin(), value).

Q10) Is forward_list::size() O(1)?

Answer No — it is linear in the number of elements.

Q11) Complexity of insert in the middle of a list?

Answer O(1) if you already have an iterator to the position; finding that position is O(n).

Q12) When would you choose forward_list over list?

Answer When you only traverse forward and want less memory per node.

Simple Programs

list push_front / push_back

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> L;
    L.push_back(1);
    L.push_front(0);
    L.push_back(2);
    for (int x : L) cout << x << " ";
    cout << "\n";
    return 0;
}

list remove and reverse

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> L = {1, 2, 2, 3, 2};
    L.remove(2);
    L.reverse();
    for (int x : L) cout << x << " ";
    cout << "\n";
    return 0;
}

list sort and unique

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> L = {3, 1, 2, 2, 1};
    L.sort();
    L.unique();
    for (int x : L) cout << x << " ";
    cout << "\n";
    return 0;
}

splice two lists

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> a = {1, 2};
    list<int> b = {3, 4};
    a.splice(a.end(), b);
    for (int x : a) cout << x << " ";
    cout << "\nsize b=" << b.size() << "\n";
    return 0;
}

forward_list insert_after

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {1, 3};
    fl.insert_after(fl.begin(), 2);
    for (int x : fl) cout << x << " ";
    cout << "\n";
    return 0;
}

forward_list before_begin

#include <iostream>
#include <forward_list>
using namespace std;

int main() {
    forward_list<int> fl = {10, 20};
    fl.insert_after(fl.before_begin(), 5);
    for (int x : fl) cout << x << " ";
    cout << "\n";
    return 0;
}

Problem Solving Tricks

list = doubly linked; forward_list = singly linked.
No operator[] — advance iterators.
Vector vs List: cache + index vs mid-node ops.
Insert O(1) only when iterator is already known.
Use list::sort — not std::sort.
splice moves nodes without copying values.
forward_list: insert_after / erase_after / before_begin.
Prefer vector unless you measured otherwise.
Erase invalidates only that node iterators.
forward_list::size() is O(n).
remove(value) erases all matches.
unique() needs sorted order for global uniqueness.

Practice Programs List

Build a list with push_front/back; print forward and reverse.
remove all zeros from a list of ints.
sort + unique a list with duplicates.
splice list B into the middle of list A.
Create a forward_list; insert_after the first element.
Insert at front of forward_list using before_begin.
Write Vector vs List table in comments (10 rows).
Write list vs forward_list table (8 rows).
Advance to the 4th element and erase it.
Explain in comments why std::sort fails on list.
Compare iterator invalidation: vector push_back vs list erase.
List three real apps where splice would help.