Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::list class

Reference for std::list: constant-time insertion and removal anywhere, splice, merge, sort, unique and remove, stable iterators, and when a list beats a vector.

std::list<T> is a doubly linked list. Every element lives in its own heap-allocated node with a pointer to the previous and next node. Given an iterator, inserting or erasing at that position takes constant time, and no other element moves. Iterators and references to the remaining elements stay valid when you insert or erase, which is the container's main selling point.

The price is that there is no random access (list[3] does not exist), traversal is slow because nodes are scattered in memory, and each element carries two pointers of overhead. For most programs a std::vector is faster even for insert-heavy work. Reach for list when you need stable iterators, cheap splice between lists, or elements that cannot be moved.

C++
#include <list>
std::list<int> l = {1, 2, 3};
l.push_front(0);
l.push_back(4);        // 0 1 2 3 4

Try it

C++ Inserting and erasing through iterators

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ sort, unique, merge, splice and reverse

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template <class T, class Allocator = std::allocator<T>>
class list;

// Modifiers
void push_front(const T&);   void push_back(const T&);
void pop_front();            void pop_back();
iterator insert(const_iterator pos, const T& v);
iterator erase(const_iterator pos);
template <class... A> reference emplace_front(A&&...);   // also emplace_back, emplace

// List operations
void splice(const_iterator pos, list& other);            // overloads for one element or a range
size_type remove(const T& v);                            // returns count since C++20
template <class Pred> size_type remove_if(Pred p);
size_type unique();                                      // consecutive duplicates
void merge(list& other);                                 // both lists must be sorted
void sort();            void reverse() noexcept;
Name Description
pos Iterator before which to insert or splice.
other Another list whose nodes are moved into this one.
v Value to insert or compare against.
p Predicate that returns true for elements to remove.

Returns: insert returns an iterator to the new element; erase returns the iterator after the removed one. Since C++20, remove, remove_if and unique return the number of removed elements (before that they returned void).

Errors / undefined behavior: front(), back(), pop_front() and pop_back() on an empty list are undefined. Using an iterator to an erased element is undefined. Allocation can throw std::bad_alloc.

Usage notes

  • Complexity: push_front, push_back, insert and erase at a known position are O(1); size() is O(1) (guaranteed since C++11); finding an element is O(n); sort() is O(n log n).
  • Stable iterators: only the iterators and references to erased elements are invalidated. Everything else stays valid, even after splice (the iterators then refer to the element in its new list).
  • Member functions, not algorithms: use l.sort(), l.remove(x), l.unique() and l.reverse(). std::sort needs random-access iterators and does not compile on a list. std::remove would not actually shrink the list; the member remove does.
  • splice moves nodes: it never copies or reallocates, so it works even for types that cannot be copied or moved, and it is O(1) for a whole list or a single element (a range is O(n) only because of the count update in some implementations).
  • merge assumes both lists are sorted with the same ordering and keeps it stable.
  • Memory: one allocation per element plus two pointers. Small elements pay a large overhead. Use std::pmr::list or a custom allocator if allocations dominate.
  • Singly linked alternative: std::forward_list uses less memory but only moves forward.
  • Cache behavior: traversing a list is typically several times slower than a vector of the same size, so profile before choosing it.