Liste circulare

Într-o listă circulară, ultimul nod se leagă din nou de primul, astfel parcurgerea se poate relua fără a întâlni un terminator nul. Pentru valorile 2, 5, 7, succesorul lui 7 este 2. Structura este utilă când elementele se prelucrează pe rând, la nesfârșit, de exemplu jucătorii care își așteaptă rândul, dar o buclă care așteaptă nullptr nu se mai oprește.

Într-o listă circulară, ultimul nod nu mai are legătura nulă, ci este legat de primul nod, astfel încât parcurgerea poate continua la nesfârșit. Orice nod are un succesor: în lista cu valorile 2, 5, 7 succesorul lui 7 este 2. Din acest motiv o buclă care așteaptă nullptr nu se mai oprește, iar parcurgerea completă trebuie să se oprească la revenirea în nodul de plecare, după ce acesta a fost procesat o dată. O listă goală se tratează separat, pentru că nu are un prim nod. Structura este potrivită când elementele se prelucrează în ordine ciclică: jucătorii care își așteaptă rândul, procesele care primesc pe rând timp de calcul, o numărătoare repetată.

Exemplul 1 — parcurgerea ciclică.

#include <iostream>
using namespace std;
struct Nod { int v; Nod* urmator; };
int main() {
    Nod a{2, nullptr}, b{5, nullptr}, c{7, nullptr};
    a.urmator = &b; b.urmator = &c; c.urmator = &a;
    Nod* p = &a;
    for (int k = 0; k < 4; ++k) {
        cout << p->v << " ";
        p = p->urmator;
    }
    return 0;
}

Cele patru afișări sunt 2 5 7 2. Revenirea la 2 după al treilea pas confirmă legătura circulară. Pentru o parcurgere în care fiecare nod este vizitat o singură dată, ciclul se oprește când p redevine nodul de start.

Exemplul 2 — parcurgerea completă o singură dată. Cu start = &a, se procesează întâi nodul start, apoi se avansează cu p = p->urmator și se repetă până când p == start. Se vizitează 2, 5, 7, în această ordine, iar suma valorilor este 14. Condiția de oprire testează egalitatea cu nodul de start după ce acesta a fost procesat, nu înainte, altfel nicio iterație nu ar rula; un ciclu do ... while (p != start) exprimă exact acest lucru.

Exemplul 3 — numărătoarea cu eliminare. Cinci copii, numerotați 1–5, stau în cerc; din doi în doi, un copil iese, până rămâne unul singur. Pornind de la copilul 1 și numărând 1, 2, ies pe rând copiii 2, 4, 1 și 5, iar rămâne copilul 3. Lista circulară modelează natural cercul: după ieșirea unui nod, predecesorul lui se leagă direct de succesorul lui, iar numărătoarea continuă de la acesta. Fiecare eliminare cere parcurgerea a cel mult doi pași și refacerea unei singure legături.

Inserarea într-o listă circulară. Pentru a adăuga un nod nou q după nodul p, se aplică aceleași două legături ca la lista simplă: q->urmator = p->urmator; p->urmator = q;. Dacă lista are un singur nod, nodul este legat de el însuși, iar succesorul lui este el. Din cercul $2\to 5\to 7\to 2$, inserarea valorii 6 după 5 dă $2\to 5\to 6\to 7\to 2$, iar parcurgerea completă dintr-un nod oarecare vizitează patru noduri.

Ștergerea unui nod. Pentru a elimina nodul de după p, se reține q = p->urmator, apoi se execută p->urmator = q->urmator;. Din cercul $2\to 5\to 6\to 7\to 2$, ștergerea nodului de după 5, adică a valorii 6, readuce lista la $2\to 5\to 7\to 2$. Dacă lista are un singur nod, p->urmator == p, iar ștergerea ar elimina chiar nodul p; acest caz se tratează separat, iar lista devine goală. La ștergerea nodului de start trebuie actualizat și pointerul start, ca să nu rămână îndreptat spre un nod eliberat.

Greșeli frecvente

• Greșit: parcurgerea unei liste circulare se oprește singură la ultimul nod.
  Corect: lista nu are nod nul; parcurgerea se oprește la revenirea în nodul de start.
• Greșit: o buclă while (p != nullptr) este potrivită pentru o listă circulară.
  Corect: nu s-ar încheia niciodată.
• Greșit: lista circulară nu poate fi goală.
  Corect: o listă fără noduri are capul nul și se tratează separat.

Înainte și după