Back to all concepts
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>
3
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

  1. What's the main advantage of std::list over std::vector?
Better cache locality
Faster random access
Less memory usage
O(1) insertion/deletion anywhere (with iterator)
  1. When should you use std::deque instead of std::vector?
When you need O(1) middle insertion
When you need the smallest memory footprint
When you want cache-friendly memory layout
When you need frequent insertion/deletion at both ends

Step Through the Code

Walk through the code step by step. Watch how variables change and see the program output at each line.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once