std::list<T> is a doubly-linked list: each element lives in its own heap-allocated node, with prev and next pointers wiring the nodes together. It gives up random access entirely and in exchange offers true O(1) insertion and erasure at any position you can name with an iterator. This chapter covers the internal structure, the operations a list supports, the splice family of constant-time list operations, iterator stability, and the question of when (if ever) you should actually pick a list in modern C++.

std::vector and std::deque both store elements close together in memory, which is great for cache behavior but means inserting in the middle requires shifting elements. For workloads that need to splice elements between sequences, move a single element from one position to another without copying it, or hold a long sequence with stable references that never go bad on insert, a linked list is the data structure that fits.

The insert itself touches only the surrounding two nodes. No element is shifted, copied, or moved. The catch is that finding the position took O(n), because the list had to be walked. A list is fast where an iterator is already in hand and slow where an index is in hand.

A std::list<T> is a sequence of nodes. Each node holds one element of type T, a pointer to the previous node, and a pointer to the next node. The list itself stores the head and tail pointers (in practice, a single sentinel node that ties the two ends together; conceptually head + tail).

Each orange box is one node on the heap. The arrows in the diagram are the next pointers (left to right) and the prev pointers (right to left). The cyan box is the list object itself, which lives on the stack (or wherever the list variable was declared) and holds the pointers to the first and last nodes.

Two consequences of this layout matter:

Walking a list is much slower than walking a vector, even though both are O(n). The vector reads sequential memory and the CPU prefetches; the list dereferences a random pointer at each step, and the CPU has to wait for each cache miss. In benchmarks, a list is often 5-10x slower than a vector for iteration over the same number of elements.

A list does not provide operator[] or at(). There is no way to jump to element 5 except by walking from one end. The standard library doesn't offer the operation because it would mask its true cost: a constant-time-looking call that's secretly O(n) is exactly the kind of thing C++ tries to avoid.

With g++ this fails with no match for 'operator[]' (operand types are 'std::list<int>' and 'int'). The container does not define the operator.

Indexed access means the wrong container. To walk the list, iterate with a range-based for or with iterators directly.

Advancing an iterator uses std::next(it, k), which steps forward k times. That call is O(k); the cost is visible at the call site, which is the point.

std::list supports push_front, push_back, pop_front, and pop_back, all in O(1). Unlike a deque, all four operations leave every existing iterator and reference valid.

The iterator grabbed before all the pushes still points at the same node, because that node hasn't moved. The push operations only touched the head or tail of the list, allocating new nodes and rewiring two pointers. Nothing else changed.

pop_front and pop_back return void, the same as deque. Read the value first to keep it.

This loop has the same shape as a deque-based version. The difference is what happens internally: each pop_front frees one heap node, where the deque version just adjusts an index inside a block.

A list excels at insert(pos, x) and erase(pos). Both are O(1) provided pos is already an iterator into the list. The list creates a new node (or destroys an existing one) and rewires the two surrounding pointers.

The std::advance(it, 2) call is O(2), which is the walk. The insert itself is O(1). When writing a list operation, separate those two costs: finding the position is the expensive part, modifying the structure is cheap.

erase returns an iterator to the next element, just like vector::erase and deque::erase.

insert and erase on a list are O(1) given an iterator. Searching for the position is still O(n). Code that does std::find followed by erase is dominated by the find cost; the list only wins when the iterator came from a cheaper source, like keeping it from an earlier traversal.

remove(value) and remove_if(predicate) are list-specific functions that walk the list and erase every node matching a value or predicate. They're O(n) overall, but they don't have to shift anything; each individual erase is constant time.

The remove member function on a list is different from the free function std::remove in <algorithm>. The free function takes any range and shuffles unwanted elements to the end without erasing them (the "erase-remove idiom" is needed to actually shorten the container). The member function on std::list does the whole thing in one call.

The function that justifies std::list's existence in modern C++ is splice. It moves one or more nodes from one list into another (or to a different position in the same list) in O(1), without copying or moving the elements. The elements themselves don't budge; only the pointers between nodes are rewired.

The retries list is empty after the splice, because its nodes were transferred into queue. No std::string was copied; no std::string was moved. The same heap-allocated string objects just have different neighbors now. For large elements this is an enormous win over the equivalent vector code, which would copy or move each element.

splice has three forms:

All three are O(1) when &a == &b or when a.get_allocator() == b.get_allocator(). The range form is O(1) on the same list and O(distance(first, last)) when the lists have different allocators, because the standard requires a size count update.

A single-node splice that reorders elements in the same list without copying:

The ORD-4 node didn't move in memory; only the pointers in the surrounding nodes changed. Any other iterator or reference to that node would still be valid and still point at ORD-4.

splice is O(1) for moving one node or a whole list between two lists with the same allocator. The equivalent vector code is O(n + m) and has to construct and destruct elements. For frequent sublist moves, list is the right container, not vector.

This is the property that, together with splice, gives std::list its identity. Once an iterator (or reference, or pointer) to a list element exists, it stays valid until that specific element is erased. No other operation invalidates it. Not push_back, not push_front, not insert somewhere else, not splice of unrelated nodes.

The splice row is the unusual one: an iterator into the source list remains valid after the splice, and now refers to a node in the destination list. The standard explicitly guarantees this. No other container can offer it.

This property makes std::list worth knowing about even in code that mostly uses std::vector. Some designs, like a workflow engine where each node has a stable identity that other components hold pointers to, depend on the stability guarantee to build a correct API.

A std::list cannot be sorted with std::sort from <algorithm>, because std::sort requires random-access iterators and a list provides only bidirectional ones. The list class exposes its own sort member function instead.

The member sort is implemented as a merge sort that operates by rewiring node pointers, so it doesn't copy any elements and runs in O(n log n) time with O(log n) auxiliary space. The standard guarantees it's a stable sort: equal elements keep their relative order.

unique removes consecutive duplicates. It does not sort first; it only collapses runs of equal values that are already adjacent. The common pattern is to sort, then call unique.

The first unique collapsed the two consecutive "books" and the three consecutive "audio" but left the trailing "books" alone because it wasn't adjacent to another "books". Sort first to put duplicates next to each other.

merge(other) combines two sorted lists into one sorted list, splicing nodes (not copying). After the call, other is empty. reverse() reverses the list in place, rewiring prev and next pointers across the whole list. Both are O(n).

merge requires both inputs to already be sorted, and produces a sorted result. If they're not sorted, the result is unspecified.

Two numbers to keep in mind: size() is O(1) since C++11 (some older STL implementations made it O(n)), and the iteration constant factor is much worse than vector even though the big-O is the same.

Modern C++ guidance, including the C++ Core Guidelines, is to default to std::vector and switch only with a specific reason. The reasons for std::list are:

The reasons not to use a list:

A practical rule: list candidates from "insertion in the middle is O(1)" should be measured first. The "find the position" step is usually O(n) anyway, and walking a vector to find a position is faster than walking a list. The vector wins many benchmarks even on workloads that look list-shaped on paper.

The example below shows the canonical case where list does win: an LRU-style "most recently used" tracker. The hot path moves the touched item to the front of a list, which is splice on a single node, O(1).

Three things make this design work and they're all list properties:

A std::vector cannot do this. A std::deque cannot do this either, because push_front invalidates all iterators. The list is the right tool for this specific job.