Construiești o listă de numere care crește oricât, fără o dimensiune fixată dinainte. Adaugi pătratele de la 1 la 5, ștergi câteva, mai adaugi unul și afișezi lista.
lista.cpp, în consolă
1 4 9 16 25
4 16 36
Prima parte din trei despre structuri de date. Un vector ține elementele unul lângă altul; o listă înlănțuită le ține oriunde în memorie, legate prin pointeri, ca vagoanele unui tren.
să descrii un nod: o valoare și adresa nodului următor
să creezi noduri cu new și să le legi
să parcurgi lista de la cap la coadă
să ștergi un nod fără să rupi lista
Pasul 2 din 5
Rulează-l linie cu linie
Două noduri, adăugate la începutul listei, apoi afișate. În panou, „→ nodul 2” înseamnă un pointer spre nodul cu valoarea 2, iar lista arată lanțul întreg.
Linia 10.cap arată spre primul nod. Lista e goală, deci cap e nullptr: nu arată nicăieri.
Linia 11. Prima tură, cu x = 2.
Linia 12.new Nod rezervă memorie pentru un nod și îi dă adresa lui n.
Linia 13.n->val e câmpul val al nodului spre care arată n. Primește 2.
Linia 14. Nodul nou arată spre vechiul cap, adică spre nimic.
Linia 15. Nodul nou devine capul listei.
Linia 11. A doua tură, cu x = 1. Variabila n din tura trecută a dispărut, dar nodul ei rămâne în memorie, legat de cap.
Linia 12. Încă un nod nou.
Linia 13. Valoarea lui: 1.
Linia 14. Nodul nou arată spre vechiul cap, nodul 2. Așa se leagă lanțul.
Linia 15. Nodul 1 devine cap. Lista e 1 → 2.
Linia 11. x = 0, condiția e falsă, bucla se termină.
Linia 17.p pornește de la cap. cap rămâne pe loc, ca să nu pierdem începutul.
Linia 18.p arată spre un nod, deci intră în buclă.
Linia 19. Se afișează valoarea nodului curent.
Linia 20.p sare la nodul următor.
Linia 18. Mai e un nod.
Linia 19. Se afișează 2.
Linia 20. Nodul 2 era ultimul: urm e nullptr.
Linia 18.p e nullptr, bucla se oprește.
Linia 22.main se încheie.
Gata. Adăugarea la început inversează ordinea: am adăugat 2, apoi 1, iar lista se citește 1, 2.
Prezice ieșirea
Schimbi bucla de la linia 11 în for (int x = 1; x <= 3; x++). Ce afișează programul?
Răspuns: „3 2 1”.
Fiecare nod nou intră în fața celorlalți. Ultimul adăugat, 3, ajunge primul. Pentru ordinea de adăugare îți trebuie inserarea la sfârșit, din cardul 2.
Pasul 3 din 5
Operațiile pe listă
Fragmentele stau în main, sub structura de mai jos. new Nod{x, cap} creează un nod și îi completează ambele câmpuri dintr-odată.
a și b sunt pointeri: țin adrese, nu noduri. -> trece de la adresă la câmp. b->urm->val se citește „valoarea nodului de după b”. Fiecare new are nevoie, la final, de un delete.
2
Adăugare la sfârșit
sfarsit.cpp
Nod *cap = nullptr;Nod *ultim = nullptr;for (int x = 1; x <= 4; x++) { Nod *n = new Nod; n->val = x * 10; n->urm = nullptr;if (cap == nullptr) cap = n;else ultim->urm = n; ultim = n;}for (Nod *p = cap; p; p = p->urm) cout << p->val << ' ';
Ce apare pe ecran
10 20 30 40
Ca să nu parcurgi toată lista la fiecare adăugare, ții minte și ultimul nod. Primul nod e caz special: devine și cap, și ultim.
3
Parcurgere și căutare
cauta.cpp
int v[5] = {4, 8, 15, 16, 23};Nod *cap = nullptr;for (int i = 4; i >= 0; i--) cap = new Nod{v[i], cap};int nr = 0, gasit = 0;for (Nod *p = cap; p; p = p->urm) { nr++;if (p->val == 15) gasit = nr;}cout << nr << ' ' << gasit;
Ce apare pe ecran
5 3
Lista nu are indici: ca să ajungi la al treilea nod, treci prin primele două. Bucla numără nodurile și ține minte poziția lui 15. În for, condiția p înseamnă p != nullptr.
4
Ștergerea unui nod
sterge.cpp
Nod *cap = nullptr;for (int x = 4; x >= 1; x--) cap = new Nod{x, cap};Nod *p = cap;while (p->urm->val != 3) p = p->urm;Nod *de_sters = p->urm;p->urm = de_sters->urm;delete de_sters;for (p = cap; p; p = p->urm) cout << p->val << ' ';
Ce apare pe ecran
1 2 4
Ca să scoți nodul 3, te oprești pe nodul dinaintea lui. Îl legi direct de nodul de după, apoi eliberezi memoria cu delete. Ordinea contează: dacă ștergi întâi, pierzi adresa nodului următor.
Capcană: treci de capătul listei
Cauți 8 într-o listă care nu-l conține. După ultimul nod, p devine nullptr, iar p->val citește de la o adresă invalidă:
„găsit” nu apare. Programul se oprește brusc, cu codul de ieșire 139, iar în terminalul Linux scrie Segmentation fault.
Repară verificând întâi pointerul: while (p != nullptr && p->val != 8). && se oprește la prima parte falsă, deci p->val nu mai e citit.
Capcană: parcurgi cu cap
Parcurgerea mută chiar cap. După prima afișare, cap e nullptr, iar a doua afișare nu mai găsește nimic:
pierdut.cpp
#include<iostream>usingnamespace std;struct Nod {int val; Nod *urm;};intmain() { Nod *cap = nullptr;for (int x = 3; x >= 1; x--) cap = new Nod{x, cap};while (cap != nullptr) { cout << cap->val << ' '; cap = cap->urm; } cout << "| ";while (cap != nullptr) { cout << cap->val << ' '; cap = cap->urm; }return0;}
Ce apare pe ecran
1 2 3 |
Repară parcurgând cu un pointer separat, Nod *p = cap;. Nodurile nu s-au șters, dar nu mai ai cum să ajungi la ele.
Pasul 4 din 5
Verifică-te
Cinci întrebări noi. După fiecare răspuns vezi imediat de ce e așa.
1 din 5 · Prezice ieșirea
Ce afișează programul?
inceput.cpp
#include<iostream>usingnamespace std;struct Nod {int val; Nod *urm;};intmain() { Nod *cap = nullptr;for (int x = 1; x <= 3; x++) cap = new Nod{x * 2, cap}; Nod *p = cap;while (p) { cout << p->val; p = p->urm; }return0;}
Răspuns: „642”.
Valorile sunt 2, 4, 6, fiecare adăugată în fața listei. Ultima adăugată, 6, e prima.
2 din 5 · Alege varianta
Ce valoare are câmpul urm al ultimului nod?
Răspuns: nullptr.
nullptr marchează sfârșitul listei, iar parcurgerile se opresc la el. O listă în care ultimul nod arată spre primul se numește circulară și are nevoie de altă condiție de oprire.
3 din 5 · Alege varianta
Vrei al 1000-lea element. De ce e mai lent într-o listă înlănțuită decât într-un vector?
Răspuns: trebuie să treci prin nodurile dinainte.
Un vector calculează direct adresa elementului. O listă știe doar unde e primul nod; fiecare alt nod se află din cel de dinainte. Lista câștigă în schimb la inserări și ștergeri.
4 din 5 · Alege varianta
Ce face p = p->urm;?
Răspuns: mută p pe nodul următor.
Se schimbă doar pointerul p. Lista rămâne neatinsă. E pasul de bază din orice parcurgere.
5 din 5 · Prezice ieșirea
Ce afișează programul?
primul.cpp
#include<iostream>usingnamespace std;struct Nod {int val; Nod *urm;};intmain() { Nod *c = new Nod{3, nullptr}; c = new Nod{2, c}; c = new Nod{1, c}; Nod *vechi = c; c = c->urm;delete vechi;for (Nod *p = c; p; p = p->urm) cout << p->val;return0;}
Răspuns: „23”.
Lista e 1, 2, 3. Capul trece pe al doilea nod, iar primul e șters cu delete. Pointerul vechi a păstrat adresa lui, ca să poată fi eliberat.
Pasul 5 din 5
Ce ai învățat
Un nod ține o valoare și adresa nodului următor. Ultimul arată spre nullptr.
Adăugarea la început e imediată și inversează ordinea. Pentru sfârșit, ții minte ultimul nod.
Parcurgi cu un pointer separat, nu cu cap, și verifici nullptr înainte de ->.
La ștergere legi întâi vecinii, apoi apelezi delete.
Programul complet
Trei funcții: adauga la sfârșit, sterge după valoare, cu cazurile cap și ultim, și afiseaza. La final, bucla din main eliberează fiecare nod.