Sequenzielle Datenstrukturen mit std::list und std::deque in C++

In C++ sind std::list und std::deque sequentielle Datenstrukturen, die in Situationen eingesetzt werden, in denen std::vector nicht ideal ist. std::list implementiert eine doppelt verkettete Liste, während std::deque (double-ended queue) schnelle Einfügungen und Löschungen an beiden Enden ermöglicht. Dieser Artikel erklärt, wann welche Struktur sinnvoll ist und zeigt praxisnahe Beispiele.

1) Was ist std::list?

std::list ist eine doppelt verkettete Liste:

• Jedes Element befindet sich in einem separaten Knoten.
• Jeder Knoten enthält Zeiger auf das vorherige und das nächste Element.
• Einfügen/Löschen in der Mitte kostet O(1).
• Kein Random Access (kein v[i]), nur Iteration.

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

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

    lst.push_front(5);   // vorne einfügen
    lst.push_back(40);   // hinten einfügen

    auto it = lst.begin();
    advance(it, 2);      // 2 Schritte vorwärts
    lst.insert(it, 25);  // in der Mitte einfügen

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

Einsatzgebiet: Wenn häufig Einfügungen oder Löschungen in der Mitte erfolgen.

2) Leistungsmerkmale von std::list

• Einfügen/Löschen in der Mitte: O(1)
• Einfügen/Löschen vorne/hinten: O(1)
• Sortierung: O(n log n), aber sehr günstig beim Verschieben.
• Kein direkter Zugriff per Index.
• Höherer Speicherverbrauch (zusätzliche Zeiger pro Knoten).

// sortieren einer Liste
list<int> lst = {5, 2, 9, 1};
lst.sort();

3) Was ist std::deque?

std::deque ist eine doppelseitige Warteschlange (Double-Ended Queue), die schnelle Operationen an beiden Enden ermöglicht.

• Schnelles Einfügen/Löschen vorne: O(1)
• Schnelles Einfügen/Löschen hinten: O(1)
• Zufälliger Zugriff: O(1)
• Einfügen/Löschen in der Mitte: O(n)
• Speicher segmentiert, nicht vollständig zusammenhängend wie 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 möglich
}

Einsatzgebiet: Wenn schnelle Operationen an beiden Enden benötigt werden.

4) Leistungsmerkmale von std::deque

• Vorne einfügen/löschen: O(1)
• Hinten einfügen/löschen: O(1)
• In der Mitte: O(n)
• Zufälliger Zugriff: O(1)
• Speicher ist segmentiert, weniger Cache-freundlich als vector.

5) Vergleich: list vs deque

6) Praxisbeispiele: Warteschlange & Entity-Verwaltung

a) Task-Warteschlange mit 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"); // priorisierte Aufgabe

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

b) Entity-Verwaltung in einer Spiel-Engine mit 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) Welche Struktur sollte man verwenden?

• list → Wenn häufig Einfügen/Löschen in der Mitte.
• deque → Wenn schnelle Operationen am Anfang und Ende erforderlich sind.
• vector → Wenn zufälliger Zugriff und Cache-Effizienz wichtig sind.

Grundregel: Zuerst vector ausprobieren. Wenn das nicht passt, deque oder list wählen.

8) TL;DR

Ähnliche Artikel