Intermediate 12 min

List and Deque

Learn std::list (doubly-linked list) and std::deque (double-ended queue) for efficient insertion and deletion operations

Learn when to use std::list and std::deque as alternatives to std::vector for specific performance requirements.

A Simple Example

#include <iostream>
#include <list>
#include <deque>

int main() {
    // std::list - doubly-linked list
    std::list<int> myList{1, 2, 3, 4, 5};

    myList.push_front(0);   // Add to front: O(1)
    myList.push_back(6);    // Add to back: O(1)

    // Insert in middle (after finding position)
    auto it = myList.begin();
    std::advance(it, 3);  // Move iterator 3 positions
    myList.insert(it, 99);  // O(1) insertion with iterator

    std::cout << "List: ";
    for (int val : myList) {
        std::cout << val << " ";  // 0 1 2 99 3 4 5 6
    }
    std::cout << "\n";

    // std::deque - double-ended queue
    std::deque<int> myDeque{10, 20, 30};

    myDeque.push_front(5);   // O(1) - efficient at front!
    myDeque.push_back(40);   // O(1)

    std::cout << "Deque: ";
    std::cout << "First: " << myDeque[0] << "\n";      // Random access O(1)
    std::cout << "Last: " << myDeque[myDeque.size()-1] << "\n";

    return 0;
}

Breaking It Down

std::list - Doubly-Linked List

What it is: Each element stores data plus pointers to previous and next elements
O(1) insertion/deletion anywhere when you have an iterator to that position
No random access - must traverse from beginning or end
Use for: Frequent insertions/deletions in middle, splice operations

std::deque - Double-Ended Queue

What it is: Hybrid structure - chunks of contiguous memory
O(1) insertion/deletion at both front and back
O(1) random access like vector
Use for: Queue operations, sliding windows, undo/redo systems

Performance Comparison

Vector: Best for random access, back operations only
List: Best for frequent middle insertions/deletions with iterators
Deque: Best for both-end operations with random access
Remember: Cache locality matters - vector often faster despite worse complexity

Why This Matters

While vector is your default choice, list and deque excel in specific scenarios.
List provides O(1) insertion and deletion anywhere (if you have an iterator), and deque gives you vector-like random access plus O(1) insertion at both ends.
Understanding their trade-offs makes you a better algorithm designer.

Critical Insight

Think of list as sticky notes connected by string - you can easily add/remove notes anywhere by cutting and tying string (changing pointers), but you can't jump to note #50 directly.

Deque is like a book with pages you can add at the front OR back easily, and you can still open to any page number quickly.

Vector is a scroll - great for reading anywhere, but adding to the front means unrolling everything!

Best Practices

Default to vector: Use vector unless you have a specific reason not to. It has the best cache locality and is usually fastest.

Use deque for both-end operations: When you need push_front and push_back with random access, deque is ideal.

Use list for middle insertions: Only choose list when you frequently insert/delete in the middle with iterators.

Measure performance: Cache effects can make vector faster than list even for middle insertions on small datasets.

Common Mistakes

Using list when you need random access: If you find yourself using std::advance often, you probably need vector or deque instead.

Forgetting deque's advantage: Many people use vector even when they need efficient front insertion - deque solves this.

Iterator invalidation: List iterators stay valid after insertion/deletion (except for deleted elements). Deque and vector invalidate differently.

Debug Challenge

This code needs efficient front insertion. Click the highlighted line to fix the container choice:

1 #include <iostream>

2 #include <vector>

4 int main() {

5 std::vector<int> nums{1, 2, 3};

6 nums.push_front(0); // Need O(1) front insertion

7 return 0;

8 }

Quick Quiz

What's the main advantage of std::list over std::vector?

O(1) insertion/deletion anywhere (with iterator)

Faster random access

Less memory usage

When should you use std::deque instead of std::vector?

When you need frequent insertion/deletion at both ends

When you want cache-friendly memory layout

When you need the smallest memory footprint

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Output:

Error:

Lesson Progress

Fix This Code
Quick Quiz
Practice Playground - run once