ReviseAlgo Logo

Standard Template Library (STL)

std::list

Doubly linked list — O(1) insertion/deletion anywhere with iterator stability

Interview: Trade-offs vs vector — when cache efficiency matters less than insertion stability

std::list

std::list is a doubly linked list — each node contains the data, a pointer to the next node, and a pointer to the previous node. It provides O(1) insertion and deletion at any known position (given an iterator) and never invalidates existing iterators or references when inserting or erasing. The trade-off: no random access and poor cache performance due to scattered memory.

When to Use std::list

std::list is rarely the right choice in modern C++. Despite O(1) insert/delete, its cache-hostile structure makes it slower than std::vector for almost all real workloads. The main legitimate uses: when iterator/pointer stability is essential (you're storing iterators into the list as references), and for splice() — moving elements between lists in O(1) without copies.

Unique Operations

splice() transfers elements from one list to another in O(1) — just re-linking pointers, no copying. remove(val) and remove_if(pred) are member functions that erase matching elements. sort() is a member function (not std::sort — list doesn't support random access iterators).

Interview Corner

Q: When would you choose std::list over std::vector?

A: Almost never, in practice. Despite the theoretical O(1) insertion, list's scattered memory layout causes constant cache misses. A vector with O(n) shift is often faster due to cache efficiency. Choose list when: (1) you need to store iterators/pointers into the list that must remain valid after insertions/deletions; (2) you heavily use splice() to move elements between lists in O(1). For interview questions, the classic answer is "list has stable iterators and O(1) insert/delete with an iterator."

Common Pitfalls

  • Using std::sort on a list: std::sort requires random access iterators — it won't compile on a list. Use the member list.sort() instead.
  • Assuming list is faster than vector for insertions: The O(1) insertion only applies to a position you already have an iterator to. Finding that position is O(n) linear scan regardless.

Best Practices

  • Default to std::vector or std::deque. Only reach for list when you specifically need iterator stability or splice.
  • Use std::forward_list if you only need singly-linked traversal — it uses less memory (no back pointer) and has the same insert/splice characteristics.