C++ list & deque: Doubly-Linked Lists & Double-Ended Queues Guide
Table of Contents
Why list and deque?
std::vector is the default sequence container in C++, and for good reason — contiguous memory means excellent cache performance. But vector has weaknesses: inserting or removing elements in the middle is O(n), and pushing to the front requires shifting every element. std::list and std::deque fill these gaps with different tradeoffs.
std::list is a doubly-linked list — O(1) insertion and removal anywhere (given an iterator), but no random access and poor cache locality. std::deque is a double-ended queue — O(1) push/pop at both front and back, plus O(1) random access, using a chunked memory layout. Understanding when each beats vector requires knowing how they work internally.
std::list — The Doubly-Linked List
#include <list>
#include <iostream>
int main() {
// Construction
std::list<int> lst = {1, 2, 3, 4, 5};
std::list<int> lst2(5, 42); // {42, 42, 42, 42, 42}
std::list<std::string> names = {"Alice", "Bob", "Charlie"};
// Push front and back — both O(1)
lst.push_front(0); // {0, 1, 2, 3, 4, 5}
lst.push_back(6); // {0, 1, 2, 3, 4, 5, 6}
lst.emplace_front(-1);
lst.emplace_back(7);
// Pop front and back — both O(1)
lst.pop_front();
lst.pop_back();
// Access: front and back only (no random access!)
std::cout << lst.front() << "\n"; // first element
std::cout << lst.back() << "\n"; // last element
// lst[2] = 99; // ERROR: no operator[] for list
// Size
std::cout << lst.size() << "\n";
std::cout << lst.empty() << "\n";
}Each node in a std::list is a separately heap-allocated object containing the element value plus two pointers (next and previous). This means list elements are scattered across memory, leading to frequent cache misses during traversal. The tradeoff: insertion and removal at any position is O(1) once you have an iterator to that position.
list Operations
#include <list>
#include <iostream>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
// Insert at position — O(1) given an iterator
auto it = lst.begin();
std::advance(it, 2); // move to 3rd element
lst.insert(it, 99); // {1, 2, 99, 3, 4, 5}
// Erase at position — O(1) given an iterator
it = lst.begin();
std::advance(it, 1);
lst.erase(it); // {1, 99, 3, 4, 5}
// Remove by value — removes ALL occurrences
lst.push_back(3);
lst.remove(3); // removes every 3
// Remove with predicate
lst.remove_if([](int x) { return x > 50; });
// Sort — uses merge sort, O(n log n)
lst.sort(); // ascending
lst.sort(std::greater<>{}); // descending
// Unique — removes consecutive duplicates (sort first!)
lst.sort();
lst.unique();
// Reverse
lst.reverse();
// Merge — merges two sorted lists
std::list<int> a = {1, 3, 5};
std::list<int> b = {2, 4, 6};
a.merge(b); // a = {1, 2, 3, 4, 5, 6}, b is now empty
// Iteration
for (const auto& val : lst) {
std::cout << val << " ";
}
}Note that std::sort() from <algorithm> requires random-access iterators, so it cannot sort a list. Use the member function list.sort() instead — it’s implemented as a merge sort that operates on the linked structure without moving data.
splice — list’s Killer Feature
splice moves nodes from one list to another in O(1) without copying or allocating. It rewires pointers directly:
std::list<int> a = {1, 2, 3};
std::list<int> b = {10, 20, 30};
// Move entire list b into a at position
auto pos = a.begin();
std::advance(pos, 1); // points to 2
a.splice(pos, b); // a = {1, 10, 20, 30, 2, 3}, b = {}
// Move single element
std::list<int> c = {100, 200, 300};
a.splice(a.end(), c, c.begin()); // moves 100 to end of a
// Move range
std::list<int> d = {7, 8, 9};
auto first = d.begin();
auto last = d.end();
std::advance(last, -1); // exclude 9
a.splice(a.begin(), d, first, last); // moves 7, 8 to front of aThis is impossible with vector or deque — moving elements between them requires copying. splice is the primary reason to choose list: when you frequently rearrange elements between collections without copying.
std::deque — The Double-Ended Queue
#include <deque>
#include <iostream>
int main() {
// Construction
std::deque<int> dq = {1, 2, 3, 4, 5};
std::deque<std::string> words(3, "hello");
// Push/pop at BOTH ends — both O(1)
dq.push_front(0); // {0, 1, 2, 3, 4, 5}
dq.push_back(6); // {0, 1, 2, 3, 4, 5, 6}
dq.pop_front(); // {1, 2, 3, 4, 5, 6}
dq.pop_back(); // {1, 2, 3, 4, 5}
// Random access — O(1) like vector!
std::cout << dq[0] << "\n"; // 1
std::cout << dq[4] << "\n"; // 5
std::cout << dq.at(2) << "\n"; // 3 (bounds-checked)
// Front and back
std::cout << dq.front() << "\n";
std::cout << dq.back() << "\n";
// Insert and erase (slower than list — O(n))
dq.insert(dq.begin() + 2, 99); // {1, 2, 99, 3, 4, 5}
dq.erase(dq.begin() + 2); // {1, 2, 3, 4, 5}
// Size and capacity
std::cout << dq.size() << "\n";
dq.shrink_to_fit(); // release unused memory
}deque combines the best of vector and list: O(1) random access like vector, plus O(1) push/pop at the front like list. The tradeoff is slightly higher per-element overhead and non-contiguous memory (elements are in chunks, not one block).
deque Internals
A deque is typically implemented as an array of pointers to fixed-size blocks (chunks). Each chunk holds several elements contiguously. The central map (array of pointers) allows growth at both ends by adding new chunks:
// Conceptual deque structure:
//
// map: [ptr0] [ptr1] [ptr2] [ptr3] [ptr4]
// | | | | |
// [...] [...] [a,b] [c,d] [e,f]
// ^^^^^^^^^^^^^^^^^^^^
// actual elements
//
// push_front: fills ptr1's block backwards
// push_back: fills ptr4's block forwards
// Both O(1) — no shifting
// Important: deque does NOT guarantee contiguous memory
std::deque<int> dq = {1, 2, 3};
// &dq[0] + 1 == &dq[1] might be true (same chunk)
// &dq[0] + 2 == &dq[2] might be FALSE (different chunks)This is why deque supports push_front efficiently — it just fills a block in reverse at the front of the map. Vector would need to shift all elements right. However, deque’s non-contiguous layout means it has worse cache performance than vector for sequential traversal.
std::forward_list
std::forward_list is a singly-linked list — each node has only a next pointer, no previous. It uses less memory per node but can only be traversed forward:
#include <forward_list>
std::forward_list<int> fl = {1, 2, 3, 4, 5};
// Only push_front — no push_back (no tail pointer)
fl.push_front(0);
// Insert AFTER a position (not before — singly-linked can't look back)
auto it = fl.begin();
fl.insert_after(it, 99); // {0, 99, 1, 2, 3, 4, 5}
// Erase AFTER a position
fl.erase_after(fl.begin()); // removes 99
// No .size() — would be O(n), violates O(1) design goal
// Use std::distance(fl.begin(), fl.end()) if needed
// Sort and unique
fl.sort();
fl.unique();
// Splice after
std::forward_list<int> fl2 = {10, 20};
fl.splice_after(fl.begin(), fl2); // moves fl2 into flUse forward_list when memory is extremely constrained and you only need forward traversal. In practice, it’s rarely used — list is more convenient, and vector is more cache-friendly.
Iterator Invalidation Rules
Understanding when iterators become invalid is critical for avoiding undefined behavior:
// std::list — most stable iterators
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = std::next(lst.begin(), 2); // points to 3
lst.push_back(6); // it still valid — points to 3
lst.push_front(0); // it still valid — points to 3
lst.erase(lst.begin()); // it still valid — points to 3
lst.erase(it); // it NOW INVALID — erased element
// Rule: list only invalidates iterators to erased elements
// std::deque — more complex
std::deque<int> dq = {1, 2, 3, 4, 5};
auto dit = dq.begin() + 2;
dq.push_back(6); // dit might be invalid!
dq.push_front(0); // dit invalidated!
// Rule: deque invalidates ALL iterators on insert/erase in the middle.
// push_back/push_front invalidate all iterators but references remain valid.
// std::vector — strictest
std::vector<int> v = {1, 2, 3};
auto vit = v.begin();
v.push_back(4); // vit invalid if reallocation occurred!
// Rule: vector invalidates all iterators on reallocation (capacity exceeded)Performance Comparison
Here’s a practical complexity comparison across the sequence containers:
// Operation vector deque list
// -------------------------------------------------------
// Random access [i] O(1) O(1) N/A
// push_back O(1)* O(1) O(1)
// push_front O(n) O(1) O(1)
// Insert in middle O(n) O(n) O(1)**
// Erase in middle O(n) O(n) O(1)**
// Find (unsorted) O(n) O(n) O(n)
// Sort O(n lg n) O(n lg n) O(n lg n)
// Splice N/A N/A O(1)
// Memory layout contiguous chunked scattered
// Cache performance excellent good poor
// Per-element overhead ~0 ~0 2 pointers
//
// * amortized ** given an iterator to position
// In PRACTICE (cache effects):
// Sequential traversal: vector >> deque >> list
// Random insertion heavy: list > deque > vector (but measure!)
// Queue (push back, pop front): deque > list > vectorCache locality matters enormously on modern hardware. Vector‘s contiguous memory means the CPU prefetcher loads upcoming elements automatically. List nodes are scattered across the heap, causing a cache miss on nearly every access. In benchmarks, vector often beats list even for middle-insertion workloads up to thousands of elements.
When to Use Each Container
std::vector — your default. Use for everything unless you have a specific reason not to. Best cache performance, lowest overhead, random access.
std::deque — when you need O(1) operations at both front and back. The natural backing container for queues. Also useful when you want random access but can’t afford vector’s front-insertion cost.
std::list — when you need O(1) insertion/removal at arbitrary positions (given iterators), when you need splice, or when you need iterator stability (iterators to non-erased elements always remain valid). Common in game engines for entity lists that frequently add/remove objects.
std::forward_list — when you need a linked list with minimal memory overhead and only forward traversal. Rare in practice.
Common Mistakes
Using list “because O(1) insert.” The O(1) only applies once you have an iterator to the insertion point. Finding that point is O(n) traversal with cache misses. For small datasets, vector’s O(n) shift with cache-friendly memory wins.
Using std::sort on a list. std::sort requires random-access iterators. Call lst.sort() member function instead.
Assuming deque is contiguous. Unlike vector, &dq[0] + n != &dq[n] in general. Don’t pass dq.data() — deque doesn’t even have a .data() method. Use vector when you need a contiguous buffer for C APIs.
Ignoring iterator invalidation. Modifying a deque invalidates all iterators. List iterators survive everything except erasing the pointed-to element. Know the rules or face undefined behavior.
Summary
std::list is a doubly-linked list with O(1) insertion/removal anywhere and O(1) splice, but poor cache performance and no random access. std::deque is a chunked array with O(1) push/pop at both ends plus O(1) random access, bridging the gap between vector and list. std::forward_list is a minimal singly-linked list. In practice, start with vector and only switch when profiling proves a different container is faster. In the next lesson, you’ll explore std::map and std::set — the sorted associative containers built on balanced binary trees.
