C++ List and Deque

The Standard Template Library gives you more than one way to store a sequence of elements, and choosing the wrong one can quietly make your program slow. std::vector is the default choice for most tasks, but when you need fast insertion and removal in the middle of a sequence, or fast growth at both ends, two other containers step in: std::list, a doubly linked list, and std::deque (pronounced \”deck\”), a double-ended queue. This lesson explains how each one is implemented internally, when to reach for it instead of std::vector, and the mistakes that trip up even experienced C++ programmers.

Overview: How List and Deque Work

std::list, defined in the <list> header, is a doubly linked list. Each element lives in its own heap-allocated node that stores the value plus two pointers: one to the previous node and one to the next node. The container itself just keeps track of the first and last node (and the size, in most implementations). Because elements are scattered across memory and connected only by pointers, std::list has no concept of \”the 5th element\” the way an array does — reaching any element requires walking the chain of pointers one node at a time, starting from either end. This makes random access, via operator[], unavailable on std::list; the container simply doesn’t support it.

What std::list is extremely good at is insertion and removal at an arbitrary position, given an iterator to that position. Because inserting a node only means allocating one new node and re-linking a couple of pointers, this is an O(1) operation, and — crucially — it does not invalidate any other iterators, pointers, or references into the list. Erasing a node is the same: O(1), and only the iterator to the erased element becomes invalid.

std::deque, defined in the <deque> header, takes a different approach. Internally, most implementations store a deque as a series of fixed-size memory blocks (\”chunks\”), plus a small internal map (an array of pointers to those chunks). This layout means a deque is not one contiguous block of memory like a std::vector, but each individual chunk is contiguous, and the map lets the container compute the address of any element in O(1) time. That is why std::deque supports fast random access with operator[] just like std::vector does, while also supporting O(1) amortized insertion and removal at both the front and the back — something std::vector cannot do efficiently at the front, since inserting at the front of a vector requires shifting every existing element.

The trade-off is that inserting or erasing in the middle of a deque is O(n), just like a vector, because elements may need to shift within or across chunks to keep the structure valid. The table below summarizes the trade-offs.

Operation std::vector std::deque std::list
Random access (v[i]) O(1) O(1) Not supported
Insert/erase at back O(1) amortized O(1) amortized O(1)
Insert/erase at front O(n) O(1) amortized O(1)
Insert/erase in middle O(n) O(n) O(1) with iterator
Memory layout Contiguous Chunked Scattered nodes

Syntax

Both containers are class templates that must be included from their own headers:

#include <list>
#include <deque>

std::list<T>  myList;
std::deque<T> myDeque;

Where T is the element type. Common construction forms work the same as other STL containers:

  • std::list<int> l; — empty list
  • std::list<int> l(5, 0); — 5 elements, each initialized to 0
  • std::list<int> l = {1, 2, 3}; — list initialized from a braced list
  • std::deque<int> d = {1, 2, 3}; — deque initialized the same way

The most commonly used member functions are:

Member function Available on Meaning
push_back(v) / push_front(v) both Insert at end / at start
pop_back() / pop_front() both Remove last / first element
front() / back() both Reference to first / last element
insert(it, v) / erase(it) both Insert/erase before/at an iterator position
operator[] / at(i) deque only Indexed access (list has neither)
sort(), merge(), splice(), unique(), remove(), reverse() list only Specialized member algorithms (see below)
size() / empty() both Number of elements / whether it’s empty

Notice that std::list has its own member versions of sort, merge, remove, and unique, instead of relying purely on the <algorithm> header. That’s because generic algorithms like std::sort require random-access iterators, which std::list doesn’t provide — so the list class implements these operations itself using pointer relinking instead of element swapping.

Examples

Example 1: std::deque basics

#include <iostream>
#include <deque>
using namespace std;

int main() {
    deque<int> dq;
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5);
    dq.push_front(1);

    for (size_t i = 0; i < dq.size(); ++i) {
        cout << dq[i] << \" \";
    }
    cout << endl;

    cout << \"Front: \" << dq.front() << \", Back: \" << dq.back() << endl;
    return 0;
}
Output:
1 5 10 20 
Front: 1, Back: 20

Each push_front adds to the beginning without shifting the existing elements, and operator[] still gives O(1) access to any position, just like a vector. This combination — fast at both ends, plus indexing — is the signature strength of std::deque.

Example 2: std::list with iterators

#include <iostream>
#include <list>
#include <iterator>
#include <string>
using namespace std;

int main() {
    list<string> names = {\"Alice\", \"Bob\", \"Charlie\"};
    names.push_back(\"Diana\");
    names.push_front(\"Zara\");

    auto it = names.begin();
    advance(it, 2); // walks two nodes forward from begin()
    names.insert(it, \"Inserted\");

    for (const string& n : names) {
        cout << n << \" \";
    }
    cout << endl;

    names.remove(\"Bob\");
    for (const string& n : names) {
        cout << n << \" \";
    }
    cout << endl;

    return 0;
}
Output:
Zara Alice Inserted Bob Charlie Diana 
Zara Alice Inserted Charlie Diana

Since std::list has no operator[], reaching a position requires an iterator plus std::advance. insert places the new element immediately before the given iterator, and remove deletes every element equal to the given value — a convenience member function you won’t find on std::vector or std::deque.

Example 3: Merging and splicing lists

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
    list<int> l1 = {1, 3, 5};
    list<int> l2 = {2, 4, 6};

    l1.sort();
    l2.sort();
    l1.merge(l2); // merges l2 into l1 in sorted order; l2 becomes empty

    cout << \"l1 after merge: \";
    for (int x : l1) cout << x << \" \";
    cout << endl;
    cout << \"l2 size after merge: \" << l2.size() << endl;

    list<int> l3 = {100, 200};
    auto it = l1.begin();
    advance(it, 3);
    l1.splice(it, l3); // moves all nodes of l3 into l1 before it, no copying

    cout << \"l1 after splice: \";
    for (int x : l1) cout << x << \" \";
    cout << endl;
    cout << \"l3 size after splice: \" << l3.size() << endl;

    return 0;
}
Output:
l1 after merge: 1 2 3 4 5 6 
l2 size after merge: 0
l1 after splice: 1 2 3 100 200 4 5 6 
l3 size after splice: 0

merge and splice are only possible this cheaply because std::list nodes can be unlinked from one list and relinked into another without copying the stored values or reallocating memory — both operations run in O(1) or O(n) in the size of the spliced range, never touching the actual element data.

How It Works Step by Step (Under the Hood)

Inserting into a std::list — say, l.insert(it, 42) — happens like this:

  1. A new node is allocated on the heap, holding the value 42 and two pointers.
  2. The new node’s next pointer is set to point to the node currently at it, and its prev pointer is set to that node’s current prev.
  3. The neighboring nodes’ pointers are updated to point to the new node instead of each other.
  4. The list’s internal size counter is incremented.

No other node moves, and no other iterator is touched — that’s why insertion is O(1) and existing iterators (other than one you explicitly erase) remain valid.

Growing a std::deque at the front, via d.push_front(v), works differently:

  1. The deque checks whether the first chunk still has free space at its front.
  2. If it does, the new element is constructed in that free slot — O(1), no allocation.
  3. If the chunk is full, a brand-new chunk is allocated, a pointer to it is added to the front of the internal map, and the element is placed in that new chunk.
  4. Because a new chunk is a fixed size (not proportional to the whole deque), this happens only occasionally, giving push_front an amortized O(1) cost — similar in spirit to how push_back on a vector is amortized O(1) even though an occasional call triggers a full reallocation.

This chunked design is also why iterators into a std::deque are fragile: inserting or erasing anywhere can shuffle which chunk holds which element, or resize the internal map, invalidating essentially all outstanding iterators and references. std::list iterators, by contrast, are invalidated only for the specific node that was erased.

Common Mistakes

Mistake 1: Trying to index a std::list

Because std::list has no random access, using operator[] on it is a compile-time error, not a runtime one:

list<int> l = {1, 2, 3, 4};
cout << l[2] << endl; // Error: std::list has no operator[]

The fix is to walk to the position with an iterator, using std::advance:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main() {
    list<int> l = {1, 2, 3, 4};
    auto it = l.begin();
    advance(it, 2);
    cout << *it << endl;
    return 0;
}
Output:
3

If you find yourself needing indexed access to a list frequently, that’s usually a sign you actually want a std::vector or std::deque instead.

Mistake 2: Using an erased iterator

Calling erase() invalidates the iterator that was passed to it. Continuing to use that iterator afterward — including implicitly, via a loop’s ++it — is undefined behavior:

list<int> l = {1, 2, 3, 4, 5};
for (auto it = l.begin(); it != l.end(); ++it) {
    if (*it == 3) {
        l.erase(it); // it is now invalid; the loop's ++it is undefined behavior
    }
}

list::erase actually returns a valid iterator to the element that followed the one erased — use that return value to keep the loop safe:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 2, 3, 4, 5};
    for (auto it = l.begin(); it != l.end(); ) {
        if (*it == 3) {
            it = l.erase(it);
        } else {
            ++it;
        }
    }
    for (int x : l) cout << x << \" \";
    cout << endl;
    return 0;
}
Output:
1 2 4 5

Mistake 3: Assuming a deque is contiguous like a vector

It’s tempting to pass &d[0] to a C-style function expecting a contiguous buffer, the way you might with std::vector. Because std::deque stores its elements in separate fixed-size chunks, this is not safe — &d[0] and &d[1] are not guaranteed to be adjacent in memory. If you need a guaranteed contiguous buffer, use std::vector instead.

Best Practices

  • Default to std::vector unless you have a measured reason to use list or deque; contiguous memory is usually faster in practice thanks to cache locality, even when Big-O analysis favors a list.
  • Reach for std::deque when you need frequent push_front/pop_front alongside indexed access — for example, a sliding window or a work queue processed from both ends.
  • Reach for std::list when you need frequent insertion or removal in the middle of a large sequence, or when you need to splice chunks of elements between containers without copying.
  • Use list::splice to move elements between lists — it relinks nodes in O(1) (for single elements) instead of copying values, and it never invalidates iterators to the moved elements.
  • When erasing while iterating a list, always capture erase()‘s return value as the new iterator rather than reusing one you just invalidated.
  • Don’t call std::sort, std::unique, or similar from <algorithm> on a std::list — use its member functions (list::sort, list::unique) since they don’t require random-access iterators and preserve node identity.
  • Treat any insert or erase on a std::deque as potentially invalidating every iterator and reference into it, unless you’ve checked your standard library’s specific guarantees.

Practice Exercises

Exercise 1: Write a program that reads integers and maintains a sliding window of the most recent 3 values using std::deque<int>. After each new value is added with push_back, pop from the front with pop_front if the window exceeds 3 elements, then print the current window.

Exercise 2: Given list<int> l = {5, 1, 4, 2, 3};, use the list’s own member functions (not std::sort) to sort it in ascending order, then use list::remove to delete every element equal to 2. Print the final list; the expected output is 1 3 4 5.

Exercise 3: Create two std::list<string> objects representing two teams. Using splice, move one player from the second team’s list to the end of the first team’s list without using push_back or copying the string. Print both lists before and after.

Summary

  • 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 stores elements in fixed-size chunks referenced by an internal map: O(1) amortized insertion/removal at both ends, plus O(1) random access via operator[].
  • Inserting into or erasing from a std::list leaves other iterators valid; almost any insert or erase on a std::deque can invalidate its iterators.
  • std::list provides its own sort, merge, splice, remove, and unique member functions because it lacks the random-access iterators that <algorithm> functions require.
  • Default to std::vector; choose std::deque for fast operations at both ends with indexing, and std::list for frequent middle insertion/removal or splicing between lists.