Sequential Data Structures with std::list and std::deque in C++

In C++, std::list and std::deque are sequential data structures that serve as alternatives to std::vector in scenarios where different performance characteristics are needed. std::list provides a doubly linked list implementation, while std::deque (double-ended queue) allows fast insertions and deletions at both ends. This article explains which structure to use in which situation, along with practical examples.

1) What is std::list?

std::list is a doubly linked list:

• Each element is stored in a separate node.
• Each node stores pointers to both the previous and next elements.
• Inserting or removing elements in the middle is O(1).
• No random access (cannot use v[i]); traversal is required.

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

int main() {
    list<int> lst = {10, 20, 30};

    lst.push_front(5);   // insert at front
    lst.push_back(40);   // insert at back

    auto it = lst.begin();
    advance(it, 2);      // move 2 steps forward
    lst.insert(it, 25);  // insert in the middle

    for (int x : lst) cout << x << " ";
}

Use Case: When frequent insertions or deletions occur in the middle of the structure.

2) std::list Performance Characteristics

• Middle insert/delete: O(1)
• Front/back insert/delete: O(1)
• Sorting (list.sort()): O(n log n), but element movement is cheap.
• No random access.
• Higher memory usage than vector (extra pointers per node).

// Sorting a list
list<int> lst = {5, 2, 9, 1};
lst.sort();   // list has its own sort algorithm

3) What is std::deque?

std::deque (double-ended queue) supports fast insertions and removals at both ends.

• Fast insertion/removal at front: O(1)
• Fast insertion/removal at back: O(1)
• Random access: O(1)
• Middle insertion/removal: O(n)
• Memory is segmented, not strictly contiguous like vector.

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

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

    dq.push_front(5);
    dq.push_back(40);

    dq.pop_front();
    dq.pop_back();

    cout << dq[0] << endl;  // random access allowed
}

Use Case: When you need fast operations on both ends.

4) std::deque Performance Characteristics

• Front insert/delete: O(1)
• Back insert/delete: O(1)
• Middle insert/delete: O(n)
• Random access: O(1)
• Memory is chunked, less cache-friendly than vector.

5) Comparison: list vs deque

6) Practical Examples: Queue and Entity Management

a) Task Queue using deque

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

int main() {
    deque<string> tasks;

    tasks.push_back("Download");
    tasks.push_back("Parse");
    tasks.push_front("Init"); // priority task

    while (!tasks.empty()) {
        cout << "Task: " << tasks.front() << endl;
        tasks.pop_front();
    }
}

b) Entity management in a game engine with list

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

struct Entity {
    string name;
    Entity(string n) : name(n) {}
};

int main() {
    list<Entity> entities;

    entities.emplace_back("Player");
    entities.emplace_back("Enemy");
    entities.emplace_back("Tree");

    for (auto it = entities.begin(); it != entities.end(); ) {
        if (it->name == "Enemy")
            it = entities.erase(it);  // O(1)
        else
            ++it;
    }

    for (auto& e : entities)
        cout << e.name << endl;
}

7) Which One Should You Use?

• Use list → When frequent insert/delete in the middle.
• Use deque → When fast front/back operations are required.
• Use vector → When random access and cache efficiency matter.

General rule: Try vector first. If it does not meet your access/modification needs, use deque or list.

8) TL;DR

Related Articles