Liste Liniare Simplu Înlănțuite

Elemente de bază și mecanismul de înlănțuire
Informatică - clasa a 11-a

Necesitatea Listelor

În dezvoltarea software, stocarea statică (vectorii) devine o barieră atunci când numărul de elemente variază constant.

🤔 Problema Vectorului: Dacă ai un vector cu 1.000.000 de elemente sortate și trebuie să inserezi un element nou pe poziția a doua, trebuie să muți la dreapta restul de 999.998 de elemente. Este un consum uriaș de resurse!

Inserarea unui element la începutul unui tablou de mari dimensiuni necesită rearanjarea întregii memorii (mutări succesive), un proces costisitor.
Asemănător, ștergerea unui element dintr-un vector necesită deplasarea spre stânga a tuturor elementelor din dreapta elementului șters

Spre deosebire de vectori, unde elementul v[i+1] este automat lângă v[i], în liste trebuie să construim noi drumul. Folosim pointerul ca o „verigă”.

Comparativ: vectori vs. liste

Caracteristică Vector (Static) Listă Simplu Înlănțuită
Alocare Memorie Bloc continuu de memorie Elemente fragmentate în HEAP
Inserare/Ștergere Lentă (necesită mutări) Rapidă (doar schimbăm adresele)

Analogia trenului: Un tren este flexibil. Fiecare vagon (nod) este independent. Pentru a adăuga marfă, doar "legi" un vagon nou oriunde, fără a reconstrui tot trenul.

Anatomia unui Nod

Nodul este unitatea fundamentală: stochează valoarea și adresa de memorie a următorului element.

5
0x200
⮕
12
0x350
⮕
7
0x410
⮕
19
NULL
struct nod {
    int info;
    nod *urm; // Pointer către următorul nod
};

Mecanismul de Înlănțuire

01. Legătură A-B-C

A(100), B(250), C(400)

02. Sortare Crescătoare

0x11(30), 0x22(10), 0x33(40), 0x44(20)

Aplicații

Inversare

X(0xA) ⮕ Y(0xB). Fă Y ⮕ X.

Eliminare (Skip)

N1(0x1) ⮕ N2(0x2) ⮕ N3(0x3).

Inserare Mijloc

A(0x10) ⮕ C(0x30). Adaugă B(0x20).

Listă Circulară

Primul(0x100), Ultimul(0x999).

Inserare Capăt

start(0xAAA). Nou nod N(0xBBB).

Terminare Listă

Termină după B(0x222).

Swap Logic (Schimb de vecini)

P(0xP) ⮕ A(0xA) ⮕ B(0xB) ⮕ S(0xS). Schimbă A cu B.