Listele inlantuite sunt formate din noduri. Fiecare nod contine un element
din lista si una sau doua legaturi, adica poineri sau referinte catre alte
noduri. Dupa configuratia legaturilor, deosebim liste simplu inlantuite,
dublu inlantuite si circulare.
- Figura 1 -
Dupa limbajul de programare folosit, legaturile pot fi realizate prin pointeri sau prin referinte. Accesul la noduri se face prin capul listei, care contine o legatura catre primul element.Nodurile pot fi parcurse secvential, de la primul catre ultimul. Daca este necesar sa se faca frecvent adaugari sau eliminari de elemente din coada listei, poate exista si o legatura directa catre coada, ca cea punctata din figura.
Intrucat nodurile sunt inlantuite intr-un singur sir, care poate fi parcurs secvential, ele pot fi indexate, ca in figura. Totusi, spre deosebire de tablou, lista nu ofera acces direct la oricare element. Pentru a ajunge la un anumit element, trebuie parcurse toate nodurile dinaintea lui.
In principiu, elementele listei poate fi continut chiar in noduri. Este posibil, insa, ca nodul sa contina numai o referinta catre elementul respectiv, ca in figura 1, Unde A, B, C, D sunt obiecte, catre care indica legaturile din noduri.
Operatiile care se pot efectua asupra unei liste simplu inlantuite punerea
unui nou element in capul listei, sau in coada listei, inserarea unui element
intre cele existente, eliminarea elementului din capul sau din coada listei,
eliminarea unui element din interior si traversarea listei (parcurgerea
ei nod cu nod, de la cap la coada).
In figura 2 este reprezentata schema adaugarii unui element
in capul listei simplu inlantuite.
Adaugarea s-a facut in urmatoarea ordine:
Toate celelalte noduri si legaturi au ramas nemodificate. remarcam, totusi, ca s-a modificat prin aceasta indexarea tuturor nodurilor. Numarul de operatii elementare necesar pentru efectuarea acestei actiuni nu depinde de lungimea listei, deci complexitatea este O(1). Amintim ca, in cazul listei implementate ca tablou, complexitatea punerii unui element in capul listei era O(n). Se observa deci, avantajul listei inlantuite din acest punct de vedere. In figura 3 este ilustrat cazul adaugarii unui element in coada listei. Si in acest caz, daca exista legatura desenata cu linie intrerupta, complexitatea este O(1). A fost necesar sa se modifice numai legatura catre coada listei si sa se adauge ultimului nod din lista anterioara o legatura catre nodul nou adaugat (legaturile colorate verde). Daca insa aceasta legatura nu exista, pentru a ajunge la ultimul element trebuie sa se plece de la cap si sa se parcurga toate celelalte elemente din lista, deci complexitatea ar fi O(n).
In figura 4 este ilustrata inserarea unui element intr-o lista. ![]() -Figura 4 - Inserarea se face astfel:
Actiunile de eliminare ale elementelor din lista sunt inverse celor prezentate mai sus si sunt echivalente cu ele in ce priveste complexitatea. |
- Figura 5 -
Ca si in cazul listei simplu inlantuite, elementele de lista pot fi continute chiar in noduri, sau nodurile pot contine doar legaturi catre elementele respective, ca in figura.
Operatiile asupra listelor dublu inlantuite sunt aceleasi ca in cazul listelor simplu inlantuite. Deosebirea consta in faptul ca, la punerea sau eliminarea unui element, trebuie modificate mai multe legaturi. Complexitatea acestor operatii este, de asemenea, aceeasi ca la listele simplu inlantuite.
- Figura 6 -
Pot exista si lista circulara dublu inlantuita, care poate fi parcursa ciclic in ambele sensuri. Aceasta se obtine din lista dublu inlantuita, la care se adauga atat o legatura de la ultimul nod catre primul, cat si una de la primul nod catre ultimul.