De ce contează?
Gândește-te la o vânătoare de comori: fiecare bilet îți spune valoarea de pe loc ȘI unde e ascuns biletul următor. Nu știi de la început câte sunt sau unde — afli mergând din bilet în bilet. Asta este o listă înlănțuită.
Ce este o listă înlănțuită?
O listă simplu înlănțuită este un lanț de noduri. Fiecare nod ține o
valoare și un pointer next către nodul următor. Ultimul nod arată spre
nullptr (capătul lanțului). Ai un pointer special, cap, spre primul nod.
3→ | 7→ | 2→ | 9→ | ∅ |
Spre deosebire de vector, nodurile NU stau lipite în memorie. Sunt împrăștiate, legate doar prin pointeri. De aici și plusurile, și minusurile listei.
Definiția nodului
struct Nod {
int val; // valoarea
Nod* next; // pointer spre urmatorul nod
};Parcurgerea listei
Pornești de la cap și urmezi next până la nullptr:
#include <iostream>
using namespace std;
struct Nod {
int val;
Nod* next;
};
void afiseaza(Nod* cap) {
for (Nod* p = cap; p != nullptr; p = p->next) {
cout << p->val << " ";
}
cout << "\n";
}De ce p != nullptr? Lista nu știe de la început câte noduri are. Te oprești
când ajungi la capăt, adică la pointerul nul.
Inserarea la început — O(1)
Cel mai ieftin loc de inserat e fix la cap: faci un nod nou, îl legi de vechiul cap și muți capul.
Nod* inserareInceput(Nod* cap, int x) {
Nod* nou = new Nod;
nou->val = x;
nou->next = cap; // noul nod arata spre fostul prim nod
return nou; // noul cap
}5→ | 3→ | 7→ | 2→ | ∅ |
Ștergerea unui nod
Pentru a șterge nodul de după p, îl ocolești cu pointerul și eliberezi memoria:
void stergeDupa(Nod* p) {
if (p == nullptr || p->next == nullptr) return; // nimic de sters
Nod* deSters = p->next;
p->next = deSters->next; // ocolim nodul
delete deSters; // eliberam memoria
}Inserarea/ștergerea sunt O(1) dacă ai deja pointerul la locul potrivit. Dar ca să ajungi acolo (al i-lea nod), parcurgi O(n). Vectorul e exact invers: acces O(1), dar inserare la mijloc O(n).
Complexitate
| Operație | Listă | Vector |
|---|---|---|
| Acces la al i-lea element | O(n) | O(1) |
| Inserare la început | O(1) | O(n) |
| Inserare după un pointer dat | O(1) | O(n) |
| Căutare după valoare | O(n) | O(n) |
Greșeli frecvente de concurs:
- Dereferențierea lui
nullptr:p->valcândp == nullptrcrapă. Testează întâi. - Pierderea restului listei: la inserare, leagă
nou->next = capÎNAINTE de a muta capul, altfel pierzi accesul la restul nodurilor. - Memory leak: după ce ocolești un nod,
delete-uiește-l. La concurs nu e fatal, dar e dezordine. - Folosești listă unde un vector e suficient: dacă ai nevoie de acces la al i-lea element, vectorul e mai bun.
Vizualizare
Urmărește cum se leagă și se dezleagă nodurile prin pointeri:
Observă că la inserare/ștergere se schimbă doar câteva săgeți, nu se mută date. Folosește ← / → pentru fiecare pas.
Recapitulare
- Un nod ține o valoare și
next; lista e un lanț care se termină înnullptr. - Inserare/ștergere O(1) dacă ai pointerul la loc; acces la al i-lea element O(n).
- Alegi lista când inserezi/ștergi des la capete/mijloc; vectorul când vrei acces direct.