Liste dublu înlănțuite

Într-o listă dublu înlănțuită, fiecare nod are legături către precedent și următor. Putem merge în ambele sensuri. Pentru nodurile 2, 5, 7, nodul cu 5 indică atât 2, cât și 7. La inserare sau ștergere trebuie actualizate toate legăturile afectate; o singură legătură uitată poate rupe parcurgerea.

Într-o listă dublu înlănțuită, fiecare nod conține o informație și două legături: una către nodul precedent (ant) și una către nodul următor (urm). Primul nod are ant = nullptr, iar ultimul are urm = nullptr. Lista poate fi parcursă în ambele sensuri: de la primul nod spre ultimul, urmând urm, sau de la ultimul spre primul, urmând ant. De aceea ștergerea unui nod pentru care există un pointer direct nu cere parcurgerea listei până la predecesor, ca la lista simplu înlănțuită. Prețul este memoria dublă pentru legături și mai multe legături de actualizat la fiecare modificare: la inserarea unui nod între p și succesorul lui trebuie refăcute patru legături (două ale nodului nou și câte una la p și la succesor), iar o singură legătură uitată rupe parcurgerea într-unul dintre sensuri. Nodurile de la capete au legături nule, deci cazurile primului și ultimului nod se tratează separat.

Exemplul 1 — inserare între două noduri. Lista $2\leftrightarrow 5$ primește valoarea 4 între ele.

#include <iostream>
using namespace std;
struct Nod { int info; Nod *ant, *urm; };
int main() {
    Nod *p = new Nod{2, nullptr, nullptr};
    Nod *r = new Nod{5, p, nullptr};
    p->urm = r;
    Nod *q = new Nod{4, p, r};
    r->ant = q;
    p->urm = q;
    for (Nod *x = p; x != nullptr; x = x->urm) cout << x->info << " ";
    cout << "| ";
    for (Nod *x = r; x != nullptr; x = x->ant) cout << x->info << " ";
    delete q; delete r; delete p;
    return 0;
}

Nodul nou q se creează cu ant = p și urm = r. Apoi r->ant și p->urm sunt refăcute să indice q. Parcurgerea înainte afișează 2 4 5, iar cea înapoi, de la ultimul nod, afișează 5 4 2; programul scrie 2 4 5 | 5 4 2. Dacă una dintre cele două legături ar fi uitată, una dintre parcurgeri ar sări peste nodul 4.

Exemplul 2 — ștergerea unui nod interior. Pentru a șterge nodul q din $2\leftrightarrow 4\leftrightarrow 5$, vecinii lui se leagă direct unul de altul: q->ant->urm = q->urm și q->urm->ant = q->ant; apoi q se eliberează. Lista devine $2\leftrightarrow 5$, cu legăturile corecte în ambele sensuri. Pentru primul nod nu există predecesor, deci doar urm->ant devine nullptr și capul avansează; pentru ultimul nod nu există succesor, deci doar ant->urm devine nullptr.

Exemplul 3 — numărarea și parcurgerea inversă. Numărul nodurilor se află parcurgând lista într-un sens, dar afișarea în ordine inversă nu cere un tablou auxiliar sau o stivă: se pornește de la ultimul nod și se urmează ant până la nullptr. Pentru lista $2\leftrightarrow 4\leftrightarrow 5$ ordinea inversă este 5 4 2. La lista simplu înlănțuită, aceeași afișare ar cere o stivă sau o recursie.

Exemplul 4 — adăugarea la sfârșit cu două capete. Dacă se păstrează și un pointer coada către ultimul nod, adăugarea la sfârșit nu cere parcurgerea listei.

void adaugaFinal(Nod *&cap, Nod *&coada, int v) {
    Nod *n = new Nod{v, coada, nullptr};
    if (coada != nullptr) coada->urm = n;
    else cap = n;
    coada = n;
}

Pornind de la o listă goală (cap și coada nule) și adăugând pe rând 3, 6 și 9: primul nod devine și cap, și coadă, deoarece coada era nul; al doilea are ant către nodul 3, iar nodul 3 primește urm către el; al treilea se leagă la fel de nodul 6. Parcurgerea de la cap dă 3 6 9, iar cea de la coada dă 9 6 3. Operația face un număr constant de pași, indiferent de lungimea listei.

Exemplul 5 — ștergerea primului nod. Pentru lista $3\leftrightarrow 6\leftrightarrow 9$, nodul 3 nu are predecesor. Ștergerea lui se face în ordinea: se reține adresa lui într-o variabilă t, cap avansează la cap->urm (nodul 6), iar ant al noului cap devine nullptr; abia apoi se eliberează t. Dacă lista are un singur nod, noul cap este nul și trebuie anulat și coada, altfel ar indica un nod eliberat. Căutarea unei valori rămâne proporțională cu lungimea listei, dar ștergerea nodului găsit nu mai cere un pointer la predecesor.

Greșeli frecvente

• Greșit: la inserare este suficient să se actualizeze legăturile urm.
  Corect: trebuie refăcute și legăturile ant, altfel parcurgerea inversă se rupe.
• Greșit: un nod interior are mereu două legături nenule.
  Corect: primul nod are ant = nullptr, iar ultimul are urm = nullptr, deci capetele se tratează separat.
• Greșit: lista dublu înlănțuită ocupă aceeași memorie ca cea simplă.
  Corect: fiecare nod are o legătură în plus.

Înainte și după