Liste simplu înlănțuite

O listă simplu înlănțuită este formată din noduri; fiecare nod păstrează o valoare și o legătură către următorul. Ultimul indică absența unui succesor. Parcurgerea pornește de la cap și urmează legăturile. Accesul la al treilea element cere trecerea prin primele două, spre deosebire de indexarea directă a unui vector.

O listă simplu înlănțuită este formată din noduri; fiecare nod conține o informație și o legătură (un pointer) către nodul următor. Ultimul nod are legătura nulă, nullptr, iar începutul listei este păstrat într-un pointer numit cap. Spre deosebire de un tablou, nodurile nu sunt consecutive în memorie și nu pot fi accesate direct după poziție: accesul la al $k$-lea element cere parcurgerea celor $k-1$ noduri dinaintea lui. În schimb, inserarea sau ștergerea după un nod cunoscut cere un număr constant de operații și nu mută alte elemente. Nodurile create cu new se eliberează cu delete. La inserarea unui nod q după nodul b, noul nod se leagă mai întâi de vechiul succesor al lui b, apoi b se leagă de q; ordinea inversă ar pierde restul listei. La ștergerea succesorului lui b, se păstrează legătura către nodul de după el înainte de eliberare.

Exemplul 1 — construire, inserare, parcurgere.

#include <iostream>
using namespace std;
struct Nod { int valoare; Nod* urmator; };
int main() {
    Nod *a = new Nod{2, nullptr};
    Nod *b = new Nod{5, nullptr};
    a->urmator = b;
    Nod *q = new Nod{6, b->urmator};
    b->urmator = q;
    for (Nod *p = a; p != nullptr; p = p->urmator)
        cout << p->valoare << " ";
    delete q; delete b; delete a;
    return 0;
}

Lista inițială este $2\to 5$. Noul nod 6 se leagă de succesorul lui 5 (care este nullptr), apoi 5 se leagă de 6. Parcurgerea de la cap afișează 2 5 6. Programul eliberează la final cele trei noduri; fiecare new are un delete corespunzător.

Exemplul 2 — inserare la început și ștergere. Inserarea la începutul listei cere schimbarea capului: nodul nou h se leagă de vechiul cap, iar capul devine h. Din $2\to 5\to 6$ se obține, după inserarea valorii 1, lista $1\to 2\to 5\to 6$. Pentru a șterge nodul cu valoarea 5, nodul aflat înaintea lui (cel cu 2) se leagă direct de nodul cu 6, apoi nodul 5 se eliberează; lista devine $1\to 2\to 6$. Suma valorilor este 9, iar numărul de noduri este 3. Dacă s-ar elibera nodul 5 înainte de refacerea legăturii, nodul 6 ar deveni inaccesibil, iar lista ar fi pierdută.

Exemplul 3 — parcurgerea cu acumulare. Suma și numărul nodurilor se calculează cu un singur pointer care avansează de la cap până la nullptr: la fiecare nod se adaugă p->valoare la sumă și se crește contorul. Parcurgerea listei $1\to 2\to 6$ dă suma 9 și numărul 3. Căutarea unei valori face cel mult atâtea comparații câte noduri are lista, deci timp proporțional cu lungimea ei.

La un fragment cu pointeri, desenează nodurile ca dreptunghiuri cu săgeți și actualizează săgețile după fiecare instrucțiune. Ordinea atribuirilor de legături decide rezultatul: q->urmator = b->urmator; b->urmator = q; inserează corect, iar ordinea inversă face ca q să indice el însuși. Parcurgerea for (p = cap; p != nullptr; p = p->urmator) vizitează fiecare nod o singură dată. Dacă se dereferențiază un pointer nul, comportamentul este nedefinit.

Exemplul 4 — urmărirea unui fragment. Lista are nodurile $2\to 5\to 8$, iar a indică nodul cu 2. Ce se afișează în urma executării secvenței de mai jos?

Nod *q = new Nod{6, a->urmator};
a->urmator = q;
for (Nod *p = a; p != nullptr; p = p->urmator)
    cout << p->valoare << " ";

• a) 2 6 5 8
• b) 2 5 6 8
• c) 2 6
• d) 6 2 5 8

Răspunsul corect este a). Nodul nou q are valoarea 6 și succesorul a->urmator, adică nodul cu 5. Apoi a->urmator = q face ca succesorul lui 2 să fie q. Lista este acum $2\to 6\to 5\to 8$, iar parcurgerea de la a afișează 2 6 5 8. Varianta c) ar apărea dacă nodul q ar fi legat de nullptr, pierzând restul listei.

Greșeli frecvente

• Greșit: elementele unei liste înlănțuite pot fi accesate direct după poziție.
  Corect: accesul cere parcurgerea nodurilor de la cap.
• Greșit: la inserare, b se leagă de noul nod înainte ca noul nod să fie legat de succesorul lui b.
  Corect: întâi se leagă noul nod de succesor, apoi se refac legăturile lui b.
• Greșit: nodurile create cu new se eliberează singure.
  Corect: fiecare new cere un delete, altfel memoria se pierde.

Înainte și după