Skip to content

Deque, List, Forward List — Double-Ended Queue, Linked Lists Performance

DodaTech Updated 2026-06-28 7 min read

In this tutorial, you will learn about Deque, List, Forward List. We cover key concepts, practical examples, and best practices to help you master this topic.

C++ deque is a double-ended queue with O(1) front and back operations and random access, while list and forward_list are linked lists offering O(1) insertion at arbitrary positions when an Iterator is available.

What You'll Learn

You will use std::deque when you need fast front and back operations with random access, use std::list for bidirectional traversal with stable iterators, use std::forward_list for memory-efficient singly-linked lists, understand iterator invalidation rules for each container, and choose the right linked structure based on your access and insertion patterns.

Why It Matters

Choosing the right sequence container significantly impacts performance. While std::vector is the default, deque is superior for queues and buffers, list excels when you need stable iterators through insertions, and forward_list is the most memory-efficient linked structure. Misunderstanding these containers leads to poor performance or incorrect code.

Learning Path

graph LR
    A["30: Vector"] --> B["31: Deque, List, Forward List"]
    B --> C["32: Set & Multiset"]
    C --> D["33: Map & Multimap"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff

std::deque

Double-ended queue: dynamic array of fixed-size blocks.

#include <iostream>
#include <deque>

int main() {
    std::deque<int> dq;
    
    // O(1) at both ends
    dq.push_back(10);
    dq.push_front(20);
    dq.push_back(30);
    dq.push_front(40);
    
    std::cout << "Front: " << dq.front() << ", Back: " << dq.back() << "\n";
    
    // Random access (O(1))
    std::cout << "dq[2] = " << dq[2] << "\n";
    
    // Iterate
    for (int x : dq) std::cout << x << " ";
    std::cout << "\n";
    
    // Pop from ends
    dq.pop_front();
    dq.pop_back();
    
    // Size and capacity-like behavior
    std::cout << "Size: " << dq.size() << "\n";
    
    // Insert at arbitrary position (O(n))
    dq.insert(dq.begin() + 1, 99);
}

Deque Characteristics

Operation Complexity
Random access O(1)
Push/pop front O(1) (amortized)
Push/pop back O(1) (amortized)
Insert in middle O(n)
Iterator invalidation (front/back push) None (most implementations)

Deque is implemented as a sequence of fixed-size blocks, not a single contiguous array. This means it can grow at both ends without moving existing elements.

std::list

Doubly-Linked List.

#include <iostream>
#include <list>
#include <algorithm>

int main() {
    std::list<int> lst = {5, 2, 8, 1, 9};
    
    // O(1) insertion at any position (with iterator)
    auto it = std::find(lst.begin(), lst.end(), 8);
    if (it != lst.end()) {
        lst.insert(it, 99);  // insert before 8
    }
    
    // Splice: transfer elements from another list (O(1))
    std::list<int> other = {100, 200, 300};
    lst.splice(lst.end(), other);  // transfers all elements
    
    std::cout << "other size: " << other.size() << "\n";  // 0
    
    // Merge two sorted lists (O(n))
    std::list<int> a = {1, 3, 5};
    std::list<int> b = {2, 4, 6};
    a.merge(b);  // a becomes {1, 2, 3, 4, 5, 6}
    
    for (int x : a) std::cout << x << " ";
    std::cout << "\n";
    
    // Sort (O(n log n))
    lst.sort();
    
    // Reverse
    lst.reverse();
    
    // Unique: remove consecutive duplicates
    lst.unique();
    
    // No random access
    // lst[3]  // Error
}

List Characteristics

Operation Complexity
Random access O(n) (not supported)
Insert at position O(1) (with iterator)
Erase at position O(1) (with iterator)
Splice O(1)
Sort O(n log n)
Iterator invalidation (insert/erase) Only the affected element

std::forward_list

Singly-linked list (C++11).

#include <iostream>
#include <forward_list>

int main() {
    std::forward_list<int> fl = {3, 1, 4, 1, 5};
    
    // No size() method (would be O(n))
    // No back() access
    // Only forward iteration
    
    // Insert after a position (not before)
    auto pos = fl.before_begin();
    for (auto it = fl.begin(); it != fl.end(); ++it) {
        if (*it == 4) break;
        ++pos;
    }
    fl.insert_after(pos, 99);
    
    // push_front only (no push_back)
    fl.push_front(0);
    
    // Splice after
    std::forward_list<int> other = {10, 20};
    fl.splice_after(fl.before_begin(), other);  // insert at front
    
    for (int x : fl) std::cout << x << " ";
    std::cout << "\n";
}

forward_list Characteristics

Operation Complexity
Forward traversal O(1) per step
Insert after O(1)
Erase after O(1)
push_front O(1)
Memory overhead 1 pointer per element (vs 2 for list)

Iterator Invalidation Comparison

Operation vector deque list forward_list
Read-only No No No No
Push/pop back Maybe Front: no, Back: no No N/A
Push/pop front N/A Front: no, Back: no No No
Insert/erase in middle Yes Yes Only erased Only erased
Reallocation All Never (no reallocation) N/A N/A

Performance Comparison

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <chrono>

template <typename Container>
double test(size_t count) {
    auto start = std::chrono::high_resolution_clock::now();
    Container c;
    for (size_t i = 0; i < count; ++i) {
        c.push_back(static_cast<int>(i));
    }
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(end - start).count();
}

int main() {
    constexpr size_t N = 1000000;
    
    std::cout << "vector:      " << test<std::vector<int>>(N) << " ms\n";
    std::cout << "deque:       " << test<std::deque<int>>(N) << " ms\n";
    std::cout << "list:        " << test<std::list<int>>(N) << " ms\n";
    std::cout << "forward_list: " << test<std::forward_list<int>>(N) << " ms\n";
}

Common Mistakes

Mistake 1: Using list When Cache Locality Matters

Linked lists have poor cache locality. Each element may be in a completely different memory page. For most workloads, vector or deque is faster even if you need occasional insertions.

Mistake 2: Calling size() on forward_list

std::forward_list does not have a size() method because it would be O(n). Track the size yourself if needed.

Mistake 3: Assuming deque is Contiguous in Memory

Although deque supports operator[], elements are NOT contiguous. You cannot pass deque.data() to a C function expecting an array.

Mistake 4: Using list::sort When You Could Sort Once

list::sort is stable O(n log n), but if you can sort while inserting, use std::set or std::priority_queue instead.

Mistake 5: Erasing During Iteration

for (auto it = lst.begin(); it != lst.end(); ++it) {
    if (*it % 2 == 0) lst.erase(it);  // it is invalidated!
}

Use it = lst.erase(it); instead, but do not increment when erasing.

Mistake 6: Using forward_list When list Would Be Simpler

forward_list only iterates forward. If you need bidirectional iteration, use list.

Practice Questions

  1. When would you choose deque over vector?
  2. What is the advantage of list over vector for insertions in the middle?
  3. Why does forward_list not have a size() method?
  4. What is the splice operation and why is it O(1)?
  5. Write code that removes every other element from a list using iterator manipulation.

Challenge

Implement a circular buffer using deque with a maximum capacity. When the buffer is full and a new element is pushed, the oldest element is automatically removed. Compare its performance with a vector-based circular buffer.

FAQ

Is `deque` always better than `vector`?

No. deque has slightly higher overhead per element access because of the block indirection. vector is better for most use cases. deque is superior when you need fast insertion at both ends.

Why does `list` have a `sort` member function?

std::sort requires random access iterators. list provides only bidirectional iterators, so it has its own sort member that uses merge sort.

Can I use `std::list` with `std::sort`?

No. std::sort requires random access iterators. Use list::sort() instead, which is stable and O(n log n).

What is the memory overhead of `list` vs `forward_list`?

Each list node stores two pointers (prev, next), plus the element. forward_list stores one pointer (next). For int, that is 16 vs 12 bytes overhead on 64-bit.

Does `deque` ever reallocate?

No, deque never moves existing elements. It allocates new blocks at the ends. This means iterators to existing elements remain valid when adding at ends.

What is the 'before_begin' iterator in forward_list?

It is a special iterator that points before the first element, used with insert_after and erase_after to operate at the front of the list.

Mini Project

Build a task scheduler using deque:

#include <iostream>
#include <deque>
#include <string>
#include <functional>

class TaskScheduler {
private:
    std::deque<std::function<void()>> tasks_;
    
public:
    void addFront(std::function<void()> task) {
        tasks_.push_front(std::move(task));
    }
    
    void addBack(std::function<void()> task) {
        tasks_.push_back(std::move(task));
    }
    
    void runAll() {
        while (!tasks_.empty()) {
            auto task = std::move(tasks_.front());
            tasks_.pop_front();
            task();
        }
    }
    
    size_t pending() const { return tasks_.size(); }
};

int main() {
    TaskScheduler scheduler;
    
    scheduler.addBack([]() { std::cout << "Task 1 (back)\n"; });
    scheduler.addBack([]() { std::cout << "Task 2 (back)\n"; });
    scheduler.addFront([]() { std::cout << "Urgent task (front)\n"; });
    
    std::cout << "Pending: " << scheduler.pending() << "\n";
    scheduler.runAll();
}

What's Next

Linked lists and deques cover sequence containers. The next lesson covers set and multiset: ordered and unordered associative containers for unique and duplicate elements.

← Previous Vector — Dynamic Array, Capacity, emplace_back, shrink_to_fit Next → Set and Multiset — Ordered and Unordered Sets, Performance

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Cpp