List

Overview

std::list implements a sequence container as a doubly-linked list, fundamentally different from std::vector in both structure and performance characteristics. Each element is stored in its own memory node, with pointers connecting it to the previous and next elements. This non-contiguous layout enables constant-time insertions and removals anywhere in the container, but sacrifices random access — you cannot use operator[] to jump directly to an element.

The primary trade-off is memory overhead. Each node carries the cost of storing two pointers (or one for std::forward_list), so for small objects, the per-element overhead can be substantial. However, for large objects or algorithms that frequently modify the container's shape, this overhead becomes negligible compared to the performance gains.

std::list provides bidirectional iterators, allowing traversal in both directions. Invalidation semantics are favorable: iterators and references to elements remain valid after insertions and removals, except for iterators to erased elements themselves.

Syntax

#include <list>

// Declaration
std::list<int> myList;
std::list<std::string> names;

// With custom allocator
std::list<double, std::allocator<double>> customList;

// Common member functions
myList.push_back(value);        // O(1) insertion at end
myList.push_front(value);       // O(1) insertion at front
myList.pop_back();              // O(1) removal from end
myList.pop_front();             // O(1) removal from front

myList.insert(iterator, value); // O(1) insertion at position
myList.erase(iterator);         // O(1) removal at position
myList.size();                  // O(n) for std::list (since C++11, O(1) guaranteed)
myList.empty();                 // O(1) check
myList.clear();                 // Remove all elements
myList.sort();                  // O(n log n) specialized sort for linked lists
myList.reverse();               // O(n) reverse in-place
myList.unique();                // O(n) remove consecutive duplicates
myList.splice(pos, other);      // O(1) move nodes from another list

// Iteration
for (auto& elem : myList) { /* ... */ }
auto it = myList.begin();
++it;  // Bidirectional: can use ++, --, but no random access

Note: Prior to C++11, size() was O(n). Since C++11, it is guaranteed O(1).

Examples

Basic insertion and removal:

#include <list>
#include <iostream>

int main() {
    std::list<int> nums = {10, 20, 30};
    
    // Insert at front and back: O(1)
    nums.push_front(5);
    nums.push_back(40);
    
    // Insert at arbitrary position: O(1)
    auto it = nums.begin();
    ++it;  // Move to second element
    nums.insert(it, 15);
    
    // Remove: O(1)
    nums.erase(it);
    
    // Output: 5 10 15 20 30 40
    for (int n : nums) {
        std::cout << n << " ";
    }
}

Splicing lists (moving nodes with zero copies):

std::list<int> list1 = {1, 2, 3};
std::list<int> list2 = {4, 5, 6};

// Move all of list2 into list1 before element 2: O(1)
auto it = list1.begin();
++it;
list1.splice(it, list2);
// list1: {1, 4, 5, 6, 2, 3}
// list2: {} (now empty)

Custom sorting (linked lists have specialized sort):

std::list<int> nums = {30, 10, 20, 50, 15};

// Uses merge sort internally, optimal for linked lists
nums.sort();  // O(n log n)
// nums: {10, 15, 20, 30, 50}

// Sort with custom comparator
nums.sort(std::greater<int>());  // Descending order

Removing duplicates:

std::list<int> nums = {1, 2, 2, 3, 3, 3, 4};
nums.unique();  // Removes consecutive duplicates: O(n)
// nums: {1, 2, 3, 4}

// With custom predicate
std::list<int> vals = {1, 2, 4, 8, 16};
vals.unique([](int a, int b) { return a * 2 == b; });

Best Practices

Use std::list when:

• You need frequent insertions/removals at arbitrary positions
• You have large objects where copying overhead matters
• Reference/iterator stability is critical
• The working set size varies dramatically

Prefer std::vector when:

• You need random access (most algorithms require it)
• Insertions/removals are rare or only at the ends
• Cache locality and memory efficiency are priorities
• The container size is stable

Specialized member functions: Always use myList.sort() instead of std::sort() on a std::list. The member function is optimized for linked-list structure and outperforms the general algorithm.

Iterator invalidation: Insertion and removal invalidate only the iterators to erased elements. This is safer than vectors, but you still must not dereference invalidated iterators.

Splicing: The splice() function is powerful for linking lists together in O(1) time without copying. Use it to reorganize elements between lists efficiently.

Common Pitfalls

Assuming O(1) size(): Pre-C++11 implementations had O(n) size(). Always assume O(1) in modern code (C++11 onward), but be aware of the historical issue when reading legacy code.

Using std::list for sequential search: Searching a list is O(n) because you must traverse linearly. Don't use std::list as a "better vector" — it only wins if you're modifying the container structure frequently.

Unexpected bidirectional-only iterators: You cannot use std::list with algorithms expecting random-access iterators. std::sort() will not compile; you must use .sort() instead. std::nth_element() and binary search algorithms also cannot work with list iterators.

Memory overhead on small types: Storing std::list<char> is wasteful. Each char is preceded by two pointers (typically 16+ bytes per node on 64-bit systems). Consider std::string or std::vector<char> instead.

Comparing with std::forward_list: Since C++11, std::forward_list is a singly-linked list that saves memory (one pointer per node) but sacrifices bidirectional iteration. Choose based on your iteration patterns.

splice — Zero-Copy Node Transfer

splice transfers nodes between lists (or within the same list) by re-pointing internal pointers only. No elements are copied or moved, so existing iterators and references to the transferred elements remain valid after the operation — they now refer into the destination list instead of the source.

Three overloads:

// (1) Transfer entire other list before pos — O(1)
list.splice(pos, other);

// (2) Transfer single element it from other before pos — O(1)
list.splice(pos, other, it);

// (3) Transfer range [first, last) from other before pos
//     O(1) if &other == this, otherwise O(distance(first, last))
list.splice(pos, other, first, last);

Example — all three overloads:

#include <list>
#include <iostream>

int main() {
    std::list<int> a = {1, 2, 3};
    std::list<int> b = {10, 20, 30};

    // (1) Move all of b into a before element '2'
    auto pos = std::next(a.begin());  // points to 2
    a.splice(pos, b);
    // a: {1, 10, 20, 30, 2, 3}   b: {}

    std::list<int> c = {100, 200, 300};

    // (2) Move single element '200' into a before element '2'
    auto it = std::next(c.begin());   // points to 200
    a.splice(pos, c, it);
    // a: {1, 10, 20, 30, 200, 2, 3}   c: {100, 300}

    std::list<int> d = {7, 8, 9};

    // (3) Move range [8, 9) into a before its end
    a.splice(a.end(), d, std::next(d.begin()), d.end());
    // a: {1, 10, 20, 30, 200, 2, 3, 8, 9}   d: {7}
}

Splicing within the same list moves a node to a new position without copying. This is the classic trick behind O(1) LRU cache promotion — the cache keeps iterators into an std::list, and accessing an entry splices its node to the front in constant time:

// Move element at 'it' to the front of the same list — O(1)
myList.splice(myList.begin(), myList, it);
// 'it' remains valid and now points to the first element

Important constraints:

• Both lists must use the same allocator — undefined behavior otherwise.
• For overload (1), the source and destination must be different list objects.
• For overload (3), pos must not be inside [first, last).

sort and unique — Linked-List-Specific Algorithms

sort

std::list provides its own .sort() member function because std::sort requires random-access iterators and cannot work with list iterators. The member version uses merge sort internally, relinks nodes instead of copying or swapping elements, and is a stable sort — equal elements preserve their relative order.

#include <list>
#include <functional>

std::list<int> nums = {8, 3, 1, 9, 5, 2};

// Default: ascending order using operator<
nums.sort();
// nums: {1, 2, 3, 5, 8, 9}

// Custom comparator: descending order
nums.sort(std::greater<int>());
// nums: {9, 8, 5, 3, 2, 1}

// Lambda comparator
std::list<std::string> words = {"banana", "apple", "fig", "cherry"};
words.sort([](const std::string& a, const std::string& b) {
    return a.size() < b.size();  // sort by length
});
// words: {"fig", "apple", "banana", "cherry"}

Key properties confirmed by cppreference:

• Complexity: approximately N·log(N) comparisons.
• No iterators or references are invalidated.
• Does not require the element type to be swappable (unlike std::sort).

unique

.unique() removes consecutive duplicate elements in O(N) comparisons, leaving only the first element of each consecutive run. This is the list equivalent of std::unique, but it actually erases the duplicates in-place rather than just moving them to the end.

std::list<int> nums = {1, 2, 2, 3, 3, 3, 2, 1, 1};
nums.unique();
// nums: {1, 2, 3, 2, 1}
// Non-consecutive duplicates are NOT removed — sort first if needed

// To remove ALL duplicates:
nums.sort();
nums.unique();
// nums: {1, 2, 3}

// Custom binary predicate (elements are "equal" if same last digit)
std::list<int> vals = {1, 11, 21, 3, 13};
vals.unique([](int a, int b) { return (a % 10) == (b % 10); });
// vals: {1, 3}

Since C++20, .unique() returns size_type — the count of removed elements.

merge — Merging Two Sorted Lists

.merge(other) absorbs all nodes from other into *this, maintaining sorted order. No elements are copied; nodes are re-pointed, like splice. The source list other becomes empty after the call.

Prerequisites: Both lists must already be sorted in the same order as the comparator. The behavior is undefined if they are not.

Contrast with std::merge: The free function std::merge reads from two input ranges and writes into a separate output — it copies elements. .merge() on a list transfers nodes with zero copies and leaves the source empty.

#include <list>
#include <iostream>

int main() {
    std::list<int> a = {1, 3, 5, 7};
    std::list<int> b = {2, 4, 6, 8};

    // Both must be sorted before merging
    a.merge(b);
    // a: {1, 2, 3, 4, 5, 6, 7, 8}
    // b: {}  — now empty

    // Custom comparator for descending-sorted lists
    std::list<int> x = {9, 7, 5};
    std::list<int> y = {8, 6, 4};
    x.merge(y, std::greater<int>());
    // x: {9, 8, 7, 6, 5, 4}
}

Stability guarantee: For equivalent elements, those from *this always precede those from other. The relative order of equal elements within each list is also preserved.

Complexity: At most (N + M - 1) comparisons, where N and M are the sizes of the two lists.

Memory Layout and Overhead

Each std::list node is a separately heap-allocated object holding the element value plus two pointers (previous and next). On a 64-bit system each pointer is 8 bytes, so the minimum per-node overhead is 16 bytes of pointer storage before even counting the allocator's own bookkeeping (typically another 8–16 bytes of block header).

A measured benchmark by Daniel Lemire found that storing 32-bit integers in std::list costs approximately 24 bytes per element on a typical 64-bit system — six times the raw data size compared to std::vector's 4 bytes per element.

Container           Bytes per 32-bit int (measured, 64-bit Linux/macOS)
std::vector         ~4    (contiguous; essentially no overhead)
std::deque          ~8    (chunked; small block header per chunk)
std::list           ~24   (2 pointers + allocator block = ~16-20 bytes overhead)
std::forward_list   ~16   (1 pointer + allocator block = ~8-12 bytes overhead)

Why this matters for cache performance: A CPU cache line is 64 bytes. A std::vector of ints packs 16 elements into one cache line. An std::list node for a single int typically spans an entire cache line (or more), and the next node is at an unpredictable address — so every pointer traversal is a potential cache miss. This is why linear scans over std::list are dramatically slower than over std::vector in practice, even though both are O(N).

std::list vs std::forward_list

std::forward_list (C++11) is a singly-linked list. It drops the prev pointer, saving 8 bytes per node on 64-bit platforms.

Choose std::forward_list when:

• You only traverse forward and never need --it.
• You insert/erase only at the front or after a known iterator.
• Memory is tight and bidirectional iteration is not needed.
• You do not need size() or push_back.

Choose std::list when:

• You need bidirectional traversal.
• You use splice to move elements between positions (including to the front of the same list for patterns like LRU caches).
• You use .merge() after sorting both lists.

std::list vs std::forward_list — Choosing the Right Node Count

The extra prev pointer in std::list costs 8 bytes per node on 64-bit systems, but it buys bidirectional traversal and the full splice/merge interface. If you only ever walk forward and insert or erase after a known iterator, std::forward_list is strictly lighter — approximately 16 bytes per int node versus 24.

The decision is usually straightforward: reach for std::forward_list when all three conditions hold — forward-only traversal, no need for push_back/pop_back, and no need for O(1) size(). As soon as one of those constraints breaks (you need --it, or you splice nodes to arbitrary positions in an LRU cache, or you call .merge() after sorting both halves), std::list is the right tool.

// C++11
#include <forward_list>
#include <list>

// forward_list: singly-linked, forward-only, no size(), no push_back
std::forward_list<int> fl = {3, 1, 4, 1, 5};
fl.sort();                        // O(n log n), same as list
fl.unique();                      // remove consecutive dupes
fl.push_front(0);                 // O(1) — only front insertion provided
// fl.push_back(9);               // compile error — not available

// list: doubly-linked, bidirectional, O(1) size(), push_back provided
std::list<int> dl = {3, 1, 4, 1, 5};
dl.sort();
dl.push_back(9);                  // O(1)
auto it = dl.end();
--it;                             // bidirectional: walk backwards
dl.splice(dl.begin(), dl, it);   // move last element to front — O(1)

One practical signal: if your data structure stores a "cursor" iterator that you move both forward and backward (e.g., an editor gap buffer or a playlist), bidirectional iteration is non-negotiable and std::list is the correct choice. For a simple event queue processed in FIFO order, std::forward_list or std::deque is lighter.

Iterator Stability — Surviving Insertions and Erasures

Unlike std::vector, which can relocate its entire buffer on a push_back, std::list never moves an existing node. An iterator, pointer, or reference to an element survives any insertion and survives erasures of other elements — the only iterator that becomes invalid is the one passed to erase itself.

This guarantee unlocks patterns that are impossible with vector: you can hand out an iterator to a caller, let them hold it across a series of insertions elsewhere in the list, and it will still be valid and still point to the same logical element.

// C++11
#include <list>
#include <iostream>

int main() {
    std::list<int> data = {10, 20, 30, 40, 50};

    // Cache an iterator into the middle of the list
    auto saved = std::next(data.begin(), 2);  // points to 30

    // Insert and erase elsewhere — saved remains valid
    data.push_back(60);
    data.push_front(5);
    data.erase(data.begin());      // erase the 5 we just inserted

    std::cout << *saved << "\n";   // still prints 30 — iterator never moved
}

LRU cache via iterator stability and splice. A classic LRU (Least Recently Used) cache combines an std::list for access-order tracking with an std::unordered_map whose values are iterators into the list. Because iterators stay valid after splice, accessing an item is a single O(1) pointer-relink to move it to the front — no lookup into the map is needed after the initial find.

// C++11
#include <list>
#include <unordered_map>
#include <optional>

template <typename Key, typename Value>
class LRUCache {
    int capacity_;
    std::list<std::pair<Key, Value>> order_;
    std::unordered_map<Key, typename std::list<std::pair<Key,Value>>::iterator> index_;

public:
    explicit LRUCache(int cap) : capacity_(cap) {}

    std::optional<Value> get(const Key& key) {
        auto it = index_.find(key);
        if (it == index_.end()) return std::nullopt;

        // Move this node to the front — O(1), iterator remains valid
        order_.splice(order_.begin(), order_, it->second);
        return it->second->second;
    }

    void put(const Key& key, Value value) {
        if (auto it = index_.find(key); it != index_.end()) {
            it->second->second = std::move(value);
            order_.splice(order_.begin(), order_, it->second);
            return;
        }
        if (static_cast<int>(order_.size()) == capacity_) {
            index_.erase(order_.back().first);
            order_.pop_back();                 // evict LRU entry — O(1)
        }
        order_.push_front({key, std::move(value)});
        index_[key] = order_.begin();
    }
};

The map stores iterators, not indices or pointers-to-value, precisely because list iterators are stable under all mutations except their own erasure.

std::erase and std::erase_if (C++20)

C++20 introduced free-function std::erase and std::erase_if for all standard containers, replacing the old remove/remove_if + erase two-step idiom. For std::list this is especially clean: the old idiom worked, but required remembering that std::remove does not actually erase — it rearranges and returns a new logical end, leaving dead elements at the tail until erase cleans them up.

With C++20, the intent is expressed in one call and the count of removed elements is returned as a size_type.

// C++20
#include <list>
#include <algorithm>  // std::erase, std::erase_if

std::list<int> nums = {1, 2, 3, 4, 5, 6, 7, 8};

// Remove all occurrences of a specific value
auto removed = std::erase(nums, 4);
// nums: {1, 2, 3, 5, 6, 7, 8}   removed == 1

// Remove all even numbers
auto count = std::erase_if(nums, [](int n) { return n % 2 == 0; });
// nums: {1, 3, 5, 7}   count == 3

For comparison, the pre-C++20 idiom required an extra erase call and was easy to write incorrectly:

// C++17 — the old two-step (still valid, but more verbose)
#include <list>
#include <algorithm>

std::list<int> nums = {1, 2, 3, 4, 5, 6};

// remove_if moves "kept" elements forward and returns iterator to new end
// For std::list, the member .remove_if() is equivalent and preferred
nums.remove_if([](int n) { return n % 2 == 0; });
// nums: {1, 3, 5}
// Note: list has its own .remove() / .remove_if() members that erase in-place
// The std::remove + erase idiom is for vector/deque, not needed for list

std::list is actually the one sequence container that had its own .remove() and .remove_if() member functions since C++98, so the two-step erase-remove idiom was never required for list. The C++20 free functions unify the spelling across all containers and are now the canonical spelling.

Cache Performance — When a Sorted Vector Beats a Sorted List

Pointer chasing is the hidden cost of every list traversal: each ++it dereferences a pointer to an address that the CPU has likely not seen before, causing a cache miss. Modern CPUs fetch 64-byte cache lines; a contiguous std::vector of 32-bit ints packs 16 elements into one cache line, so a linear scan reads the next 15 values essentially for free after the first miss. An std::list node typically occupies an entire cache line for a single value, and the next node is at an unpredictable heap address — potentially in a different memory page.

Benchmarks consistently show that for containers of up to tens of thousands of small elements, iterating a sorted std::vector is 5–10× faster than iterating a sorted std::list, even though both are O(N).

// C++17
#include <vector>
#include <list>
#include <algorithm>

// Inserting into sorted order: O(n) scan for both, but vector copy-shifts tail
void insert_sorted_list(std::list<int>& c, int val) {
    auto pos = std::find_if(c.begin(), c.end(), [val](int x){ return x > val; });
    c.insert(pos, val);  // O(1) pointer relink — no element copies
}

void insert_sorted_vec(std::vector<int>& c, int val) {
    auto pos = std::lower_bound(c.begin(), c.end(), val); // O(log n) binary search
    c.insert(pos, val);  // O(n) shift — but cache-friendly memcpy/memmove
}

// For small N (< ~10 000 ints), insert_sorted_vec wins despite O(n) shift
// because lower_bound uses SIMD-friendly contiguous memory and the shift
// is a single cache-efficient memmove.

The crossover point depends on element size. For large objects (e.g., structs of 256 bytes), the copy cost of shifting a vector eventually dominates, and std::list's O(1) pointer relink wins. For pointer-sized or smaller values, the vector's cache advantage is so large that it wins even with N in the hundreds of thousands.

Rule of thumb: default to std::vector, profile before switching to std::list, and consider a sorted std::vector with lower_bound before accepting the cache penalty of a linked list. std::list is the right tool when insert/erase positions are provided as iterators (not values to search for), when you use splice to avoid copies entirely, or when iterator stability under mutation is a hard requirement.

See Also

• std::forward_list — Singly-linked list (C++11); lighter-weight but forward-iteration only
• std::vector — Dynamic array; faster for random access and cache locality
• std::deque — Double-ended queue; supports O(1) operations at both ends with random access
• std::array — Fixed-size contiguous container; for when size is known at compile time
• Iterators and ranges — Understanding bidirectional iteration and range operations