Pointeri, alocare dinamică și liste înlănțuite C++

Un pointer păstrează adresa unui obiect, iar alocarea dinamică permite crearea unor obiecte a căror durată de viață este controlată explicit sau printr-un proprietar automat. O listă înlănțuită folosește noduri conectate prin pointeri și face vizibile aceste concepte.

Vom construi o listă simplu înlănțuită, vom șterge prima apariție a unei valori și vom elibera toate nodurile. Exemplul explică mecanismul; în aplicații obișnuite preferăm containerele standard și proprietatea automată a resurselor când acestea exprimă cerința.

Cum funcționează

Pentru un obiect int x, expresia &x produce adresa lui, iar un pointer int* p poate păstra acea adresă. Expresia *p accesează obiectul indicat, numai dacă pointerul este valid. nullptr reprezintă absența unui obiect. Un pointer neinițializat nu este echivalent cu nullptr, iar unul către un obiect deja distrus nu devine automat sigur.

Operatorul new Node creează un nod și întoarce adresa lui. delete distruge nodul și eliberează memoria. După delete, nu mai citim câmpurile acelui nod. Pentru alocarea unui tablou prin new T[n] ar fi necesar delete[], nu delete; exemplul alocă numai noduri individuale. Dacă o alocare new obișnuită eșuează, poate arunca o excepție, nu trebuie presupus că întoarce nullptr.

Lista are un pointer head spre primul nod și tail spre ultimul. Fiecare nod conține valoarea și next, adresa următorului. Lista goală are ambii pointeri nuli. La adăugare, conectăm vechiul ultim nod la cel nou sau stabilim head dacă lista era goală, apoi actualizăm tail. Parametrul Node*& este o referință la pointer, astfel încât funcția poate schimba pointerul deținut de apelant.

Pentru ștergere păstrăm nodul curent și predecesorul. Dacă găsim valoarea, legăm predecesorul direct la succesor. Pentru primul nod actualizăm head; pentru ultimul actualizăm tail. Abia după repararea legăturilor apelăm delete. La eliberarea întregii liste salvăm mai întâi next, deoarece după distrugerea nodului accesul head->next ar fi invalid.

Programul acceptă 0 <= n <= 100000, valori int și o țintă. Fiecare nod are un singur proprietar conceptual, lista. Codul prezintă gestionarea manuală pe calea normală de execuție; pentru siguranță la excepții și reutilizare într-o clasă sunt necesare reguli de proprietate complete sau RAII, de exemplu containere standard ori unique_ptr. Copierea simplă a lui head ar copia adresa, nu toate nodurile.

Exemplu urmărit pas cu pas

Pentru lista 2→5→2 și ținta 2, primul nod este eliminat, iar head devine nodul cu 5. tail rămâne ultimul nod cu 2. Rezultatul este 5→2, deoarece cerința elimină numai prima apariție.

Pentru o listă cu un singur nod egal cu ținta, după ștergere atât head, cât și tail sunt nuli. Pentru o țintă absentă nu schimbăm legăturile. Aceste situații sunt la fel de importante ca ștergerea din mijloc, deoarece afectează capetele structurii.

Implementare C++17

#include <iostream>
struct Node {
    int value;
    Node *next;
};
void append(Node *&head, Node *&tail, int x) {
    Node *p = new Node{x, nullptr};
    if (tail)
        tail->next = p;
    else
        head = p;
    tail = p;
}
void eraseFirst(Node *&head, Node *&tail, int x) {
    Node *previous = nullptr;
    Node *current = head;
    while (current && current->value != x) {
        previous = current;
        current = current->next;
    }
    if (!current)
        return;
    if (previous)
        previous->next = current->next;
    else
        head = current->next;
    if (tail == current)
        tail = previous;
    delete current;
}
int main() {
    int n;
    std::cin >> n;
    Node *head = nullptr;
    Node *tail = nullptr;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        append(head, tail, x);
    }
    int target;
    std::cin >> target;
    eraseFirst(head, tail, target);
    for (Node *p = head; p; p = p->next)
        std::cout << p->value << ' ';
    std::cout << '\n';
    while (head) {
        Node *next = head->next;
        delete head;
        head = next;
    }
    tail = nullptr;
}

De ce funcționează și cât costă

Lista păstrează invariantul unui lanț terminat cu nullptr și al unui tail care indică ultimul nod. Ștergerea înlocuiește exact legătura către nodul eliminat cu legătura către succesor, păstrând ordinea celorlalte noduri. Eliberarea finală distruge fiecare nod rămas o singură dată.

Adăugarea la sfârșit cu tail costă O(1). Căutarea și ștergerea primei apariții costă O(n), deoarece trebuie găsit nodul. Memoria este O(n), cu un pointer suplimentar per nod. Accesul la poziția i nu este constant ca într-un tablou.

Greșeli frecvente

Nu accesa pointeri după delete și nu elibera aceeași adresă de două ori. Nu pierde head înainte de curățare, altfel memoria poate deveni inaccesibilă. Nu confunda ștergerea pointerului local cu ștergerea obiectului indicat.

Exersează

Ce pointeri trebuie actualizați când ștergi singurul nod al unei liste?

Rezolvare explicată: head devine nullptr prin succesorul absent, iar tail devine predecesorul absent, tot nullptr. Nodul este apoi eliberat exact o dată.

Continuă să înveți

Parametri, structuri și vector.

Întrebări frecvente

Ce diferență există între pointer și obiect?

Pointerul păstrează o adresă. Obiectul este valoarea aflată la acea adresă. Copierea pointerului nu copiază automat obiectul sau întreaga listă.

De ce folosim Node*& la capul listei?

Funcția trebuie să poată modifica pointerul apelantului, de exemplu când primul nod este șters. Referința la pointer transmite tocmai această posibilitate.

delete pune pointerul pe nullptr?

Nu. După eliberare, variabila poate păstra o adresă devenită invalidă. Actualizarea pointerilor trebuie făcută explicit sau gestionată printr-un proprietar automat.

De ce salvăm next înainte de delete?

După distrugerea nodului, citirea câmpului next este invalidă. Salvarea adresei succesorului înainte de ștergere permite continuarea în siguranță.

Lista este mereu mai rapidă decât vectorul la ștergere?

Nu. Relegarea poate fi constantă când ai deja poziția necesară, dar găsirea nodului costă timp. Vectorul oferă acces direct și localitate bună a memoriei, deci alegerea depinde de operații.