Liste dublu înlănțuite — legături în ambele sensuri

De ce contează?

O listă simplu înlănțuită e ca un drum cu sens unic: poți merge doar înainte. O listă dublu înlănțuită e ca o stradă cu două sensuri — de la fiecare nod poți merge și înainte, și înapoi.

Ce aduce nou?

O listă dublu înlănțuită adaugă fiecărui nod un al doilea pointer, prev, spre nodul anterior. Acum poți parcurge lista în ambele sensuri și poți șterge un nod dat fără să-i cauți predecesorul.

struct Nod {
    int val;
    Nod* prev;   // nodul anterior
    Nod* next;   // nodul urmator
};

∅

⇄3⇄

7⇄

2⇄

9⇄

∅

Fiecare nod are legături în ambele sensuri (prev și next); capetele indică ∅.

Observația-cheie

Primul nod are prev = nullptr, ultimul are next = nullptr. Restul au ambele legături valide. Asta îți permite să pleci din orice nod în orice direcție.

Ștergerea unui nod dat — O(1)

Aici strălucește lista dublă: ai un pointer la nodul de șters și îl ocolești relegând vecinii, fără a parcurge nimic.

#include <iostream>
using namespace std;

struct Nod {
    int val;
    Nod* prev;
    Nod* next;
};

void sterge(Nod* nod) {
    if (nod == nullptr) return;
    if (nod->prev) nod->prev->next = nod->next;  // vecinul stang sare peste nod
    if (nod->next) nod->next->prev = nod->prev;  // vecinul drept sare peste nod
    delete nod;
}

De ce verificăm if (nod->prev) și if (nod->next)? Dacă nodul e la un capăt, unul dintre vecini lipsește (nullptr); fără verificare ai dereferenția un pointer nul.

Inserarea după un nod dat — O(1)

void inserareDupa(Nod* nod, int x) {
    Nod* nou = new Nod;
    nou->val = x;
    nou->prev = nod;
    nou->next = nod->next;
    if (nod->next) nod->next->prev = nou;  // legam vecinul drept inapoi
    nod->next = nou;                       // legam nodul curent de cel nou
}

Observația-cheie

Ordinea relegării contează: setează legăturile noului nod și ale vecinului din dreapta ÎNAINTE de a rupe nod->next, altfel pierzi accesul la restul listei.

Când o folosești?

Lista dublă e baza pentru structuri unde ștergi/inserezi des la poziții cunoscute: implementări de LRU cache, editoare de text (cursor înainte/înapoi), sau std::list din STL, care e fix o listă dublu înlănțuită.

Complexitate

Operație	Listă dublă	Listă simplă
Ștergere nod dat	O(1)	O(n)*
Inserare după nod dat	O(1)	O(1)
Parcurgere înapoi	O(n)	imposibil direct
Acces la al i-lea element	O(n)	O(n)

* La lista simplă ai nevoie de pointerul la predecesor, deci îl cauți.

Greșeli frecvente

Greșeli frecvente de concurs:

Uiți să actualizezi prev: dacă regi doar next-urile, parcurgerea înapoi se rupe.
Dereferențiere la capete: nod->next->prev crapă dacă nod->next == nullptr. Verifică întâi.
Ordine greșită la inserare: rupi nod->next înainte de a-l salva → pierzi restul listei.
Supra-inginerie: dacă nu ai nevoie de mers înapoi sau de ștergere O(1), lista simplă (sau un vector) e suficientă.

Vizualizare

Urmărește cum se actualizează ambele legături la inserare și ștergere:

Indiciu

Observă că ștergerea atinge exact două legături: prev->next și next->prev. Folosește ← / → pentru fiecare pas.

Recapitulare

Fiecare nod are prev și next — parcurgere în ambele sensuri.
Ștergerea unui nod dat și inserarea după el sunt O(1), relegând doi vecini.
Costul: un pointer în plus per nod și două legături de actualizat; folosește-o doar când chiar ai nevoie de ambele sensuri.