Estructuras secuenciales con std::list y std::deque en C++

En C++, std::list y std::deque son estructuras de datos secuenciales que sirven como alternativas a std::vector cuando se necesitan diferentes características de rendimiento. std::list implementa una lista doblemente enlazada, mientras que std::deque (double-ended queue) permite inserciones y eliminaciones rápidas en ambos extremos. Este artículo explica en qué casos conviene usar cada una, con ejemplos prácticos.

1) ¿Qué es std::list?

std::list es una lista doblemente enlazada:

• Cada elemento se almacena en un nodo independiente.
• Cada nodo contiene punteros al elemento anterior y al siguiente.
• Insertar o eliminar en el medio cuesta O(1).
• No existe acceso aleatorio (no funciona v[i]), se debe iterar.

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

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

    lst.push_front(5);   // insertar al inicio
    lst.push_back(40);   // insertar al final

    auto it = lst.begin();
    advance(it, 2);      // avanzar 2 posiciones
    lst.insert(it, 25);  // insertar en el medio

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

Cuándo usarla: cuando se realizan muchas inserciones o eliminaciones en el medio.

2) Características de rendimiento de std::list

• Inserción/eliminación en el medio: O(1)
• Inserción/eliminación al inicio o al final: O(1)
• Ordenación (list.sort()): O(n log n), pero el desplazamiento de elementos es barato.
• No hay acceso aleatorio por índice.
• Mayor consumo de memoria (nodos con punteros extra).

// ordenar una lista
list<int> lst = {5, 2, 9, 1};
lst.sort();

3) ¿Qué es std::deque?

std::deque es una estructura de doble extremo que permite operaciones rápidas al inicio y al final.

• Inserción/eliminación al inicio: O(1)
• Inserción/eliminación al final: O(1)
• Acceso aleatorio: O(1)
• Inserción/eliminación en el medio: O(n)
• Memoria segmentada, no completamente contigua como 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;  // acceso por índice permitido
}

Cuándo usarla: cuando se necesita velocidad en operaciones al inicio y al final.

4) Características de rendimiento de std::deque

• Inicio: O(1)
• Final: O(1)
• Medio: O(n)
• Acceso aleatorio: O(1)
• Menos amigable al cache que vector debido a su memoria segmentada.

5) Comparación: list vs deque

6) Ejemplos prácticos: colas de tareas y gestión de entidades

a) Cola de tareas con 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"); // tarea prioritaria

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

b) Gestión de entidades en un motor de videojuegos usando 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) ¿Cuál deberías usar?

• list → cuando hay muchas inserciones/eliminaciones en el medio.
• deque → cuando se necesita rapidez al inicio y al final.
• vector → cuando el acceso aleatorio y la eficiencia de cache son importantes.

Regla general: Prueba primero vector. Si no satisface las necesidades, usa deque o list.

8) TL;DR

Artículos relacionados