list — lista dublu înlănțuită din STL

Ce este std::list?

std::list este o listă dublu înlănțuită gata făcută din STL. Nu mai scrii tu structura cu prev și next și nu mai jonglezi cu new/delete — STL ține nodurile și pointerii pentru tine. Tu primești operații sigure: adaugi la capete, inserezi sau ștergi cu un iterator, parcurgi în ambele sensuri.

De ce ai vrea asta în loc de vector? Pentru că la list inserarea și ștergerea la mijloc, când ai deja iteratorul spre poziție, sunt O(1): relegi doi-trei pointeri și gata. La vector, aceleași operații mută O(n) elemente.

Prețul: nu există acces direct la al i-lea element. Nu poți scrie l[3], fiindcă nodurile sunt împrăștiate în memorie. Ajungi la un element doar mergând din nod în nod, cu un iterator.

Cum arată, pas cu pas

Pornim de la o listă goală și o construim:

• push_back(7) → [7]
• push_back(2) → [7, 2]
• push_front(9) → [9, 7, 2] (adaugă în față)
• pop_back() → [9, 7] (scoate ultimul)

Acum vrem să inserăm 5 înaintea lui 7. Ne plasăm cu un iterator pe 7 și chemăm insert:

• insert(it_spre_7, 5) → [9, 5, 7]

Niciun element nu s-a mutat în memorie. S-a creat un nod nou și s-au rescris câteva legături. Asta e magia O(1) a listei.

Implementare C++

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

int main() {
    list<int> l;

    l.push_back(7);          // [7]
    l.push_back(2);          // [7, 2]
    l.push_front(9);         // [9, 7, 2]
    l.pop_back();            // [9, 7]

    // Parcurgere cu iterator (NU exista l[i] la list)
    cout << "Lista: ";
    for (list<int>::iterator it = l.begin(); it != l.end(); ++it) {
        cout << *it << " ";  // afiseaza: 9 7
    }
    cout << "\n";

    // Cautam nodul cu valoarea 7 si inseram 5 INAINTEA lui
    list<int>::iterator p = l.begin();
    while (p != l.end() && *p != 7) {
        ++p;                 // avansam pas cu pas pana gasim 7
    }
    if (p != l.end()) {
        l.insert(p, 5);      // insert pune INAINTEA pozitiei -> [9, 5, 7]
    }

    // Stergem nodul cu valoarea 5 (p inca arata spre 7, mergem cu un pas inapoi)
    list<int>::iterator q = l.begin();
    while (q != l.end() && *q != 5) {
        ++q;
    }
    if (q != l.end()) {
        l.erase(q);          // sterge nodul si returneaza iterator spre urmatorul -> [9, 7]
    }

    // Afisare finala
    cout << "Final: ";
    for (int x : l) {        // for-each merge la fel de bine
        cout << x << " ";    // afiseaza: 9 7
    }
    cout << "\n";

    // splice: muta elementele dintr-o lista in alta in O(1), fara copiere
    list<int> a = {1, 2, 3};
    list<int> b = {10, 20};
    a.splice(a.end(), b);    // muta tot b la finalul lui a
    // acum a = [1, 2, 3, 10, 20] si b = [] (golit, fara copiere de elemente)

    cout << "Dupa splice a: ";
    for (int x : a) {
        cout << x << " ";    // afiseaza: 1 2 3 10 20
    }
    cout << "\n";

    return 0;
}

splice e operația-vedetă a listei: mută noduri întregi dintr-o listă în alta fără a copia valori — doar reagață pointerii. La un vector așa ceva ar însemna copierea efectivă a tuturor elementelor.

Complexitate

Recapitulare

• std::list e o listă dublu înlănțuită gata făcută: push_front/push_back, pop_front/pop_back, plus insert/erase cu iterator în O(1).
• Nu are acces cu [] — parcurgi mereu cu iteratori (sau for-each); accesul la al i-lea element e O(n).
• Preferă list doar la inserări/ștergeri dese la mijloc cu iterator cunoscut; altfel vector e de obicei mai rapid în practică din cauza cache-ului.