list & deque

Alongside std::vector, the STL provides two other general purpose sequence containers with different performance trade-offs: std::list, a doubly-linked list, and std::deque, a double-ended queue. Both are useful in specific situations, but neither should replace vector as your default.

std::list — a doubly-linked list

std::list<T> stores each element in its own separately allocated node, with pointers linking each node to its neighbors in both directions. This makes inserting or removing an element anywhere in the list — front, back, or middle — an O(1) operation once you already have an iterator pointing at the spot, because it only involves relinking a few pointers, never shifting other elements. The trade-off is that list has no [] operator at all — reaching the Nth element requires walking the list one node at a time, which is O(n).

list_basics.cpp

CPP

#include <list>
#include <iostream>

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

    nums.push_front(5);   // O(1) — {5, 10, 20, 30}
    nums.push_back(40);   // O(1) — {5, 10, 20, 30, 40}

    // Insert 99 right before the iterator pointing at 20.
    auto it = std::find(nums.begin(), nums.end(), 20);
    nums.insert(it, 99);  // O(1) once "it" is known — {5, 10, 99, 20, 30, 40}

    for (int n : nums) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    // nums[2]; // does NOT compile — list has no operator[]

    return 0;
}

std::deque — a double-ended queue

std::deque<T> (usually pronounced “deck”) supports fast O(1) insertion and removal at both ends — unlike vector, which is only fast at the back. Internally, a deque is typically implemented as a sequence of fixed-size blocks rather than one contiguous array, which is what allows growth at the front without shifting every element. Unlike list, deque still supports [] random access in O(1).

deque_basics.cpp

CPP

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {10, 20, 30};

    dq.push_front(5);   // O(1) — {5, 10, 20, 30}
    dq.push_back(40);   // O(1) — {5, 10, 20, 30, 40}

    std::cout << dq[0] << std::endl;  // 5 — random access works, like vector
    std::cout << dq[2] << std::endl;  // 20

    dq.pop_front();     // O(1) — {10, 20, 30, 40}
    dq.pop_back();      // O(1) — {10, 20, 30}

    return 0;
}

Comparing vector, list, and deque

Operation / property	vector	list	deque
Random access (`[]`)	O(1)	Not supported	O(1)
Insert/remove at back	O(1) amortized	O(1)	O(1)
Insert/remove at front	O(n)	O(1)	O(1)
Insert/remove in middle	O(n) — shifts elements	O(1) with an iterator	O(n) — shifts elements
Memory layout	One contiguous block	Scattered nodes, linked by pointers	Multiple fixed-size blocks
Cache friendliness	Excellent	Poor (pointer chasing)	Good

Default to vector

In practice, std::vector outperforms list for most workloads even when the “theoretical” complexity favors list — its contiguous memory layout is dramatically friendlier to the CPU cache, which often matters more than raw big-O in real-world code. Reach for list only when you genuinely need frequent insertion/removal in the middle of a large sequence and already hold iterators to the right spots, and reach for deque when you specifically need fast operations at both ends (a common building block for implementing a queue — in fact, std::queue uses deque internally by default).

Iterator invalidation differs too

Inserting or removing elements in a vector or deque can invalidate iterators and references to other elements (because memory may be reallocated or shifted). list iterators, by contrast, remain valid even after insertions or removals elsewhere in the list — only an iterator to an erased element itself becomes invalid. This is another reason list is occasionally chosen despite its weaker cache behavior.

std::list — doubly-linked list; O(1) insert/remove anywhere given an iterator, no random access.
std::deque — double-ended queue; O(1) push/pop at both front and back, supports [].
Default to std::vector unless you specifically need one of these characteristics.