Listele înlănțuite sunt formate din noduri. Fiecare nod conține un
element din listă și una sau două legături, adică pointeri sau
referințe către alte noduri. După configurația legăturilor, deosebim
liste simplu înlănțuite, dublu înlănțuite și circulare.
- Figura 1 -
După limbajul de programare folosit, legăturile pot fi realizate prin pointeri sau prin referințe. Accesul la noduri se face prin capul listei, care conține o legatură către primul element.Nodurile pot fi parcurse secvențial, de la primul către ultimul. Dacă este necesar să se facă frecvent adăugări sau eliminări de elemente din coada listei, poate exista și o legatură directă către coadă, ca cea reprezentată punctat în figură.
Întrucât nodurile sunt înlănțuite într-un singur șir, care poate fi parcurs secvențial, ele pot fi indexate, ca în figură. Totuși, spre deosebire de tablou, lista nu oferă acces direct la oricare element. Pentru a ajunge la un anumit element, trebuie parcurse toate nodurile dinaintea lui.
În principiu, elementele listei pot fi conținute chiar în noduri. Este posibil, însă, ca nodul să conțină numai o referință către elementul respectiv, ca în figura 1, unde A, B, C, D sunt obiecte, către care indică legăturile spre element din noduri.
Operațiile care se pot efectua asupra unei liste simplu înlănțuite
sunt: punerea unui nou element în capul listei, sau în coada listei,
înserarea unui element între cele existente, eliminarea elementului din
capul sau din coada listei, eliminarea unui element din interior și
traversarea listei (parcurgerea ei nod cu nod, de la cap la coadă).
În figura 2 este reprezentată schema adaugării unui
element în capul listei simplu înlănțuite.
Adăugarea s-a făcut în urmatoarea ordine: Toate celelalte noduri și legături au rămas nemodificate. Remarcăm, totuși, că s-a modificat prin aceasta indexarea tuturor nodurilor. Numărul de operații elementare necesar pentru efectuarea acestei acțiuni nu depinde de lungimea listei, deci complexitatea este O(1). Amintim că, în cazul listei implementate ca tablou, complexitatea punerii unui element în capul listei era O(n). Se observă deci, avantajul listei înlănțuite din acest punct de vedere. În figura 3 este ilustrat cazul adăugării unui element în coada listei. Și în acest caz, dacă există legatura desenata cu linie întreruptă, complexitatea este O(1). A fost necesar să se modifice numai legătura către coada listei și să se adauge ultimului nod din lista anterioară o legătură către nodul nou adăugat (legăturile colorate verde). Dacă însă legătura desenată cu linie întreruptă nu există, pentru a ajunge la ultimul element trebuie să se plece de la cap și să se parcurgă toate celelalte noduri din listă, deci complexitatea ar fi O(n).
În figura 4 este ilustrată înserarea unui element într-o listă. ![]() -Figura 4 - Înserarea se face astfel: Acțiunile de eliminare a elementelor din listă sunt inverse celor prezentate mai sus și sunt echivalente cu ele în ce privește complexitatea. |
- Figura 5 -
Ca și în cazul listei simplu înlănțuite, elementele de listă pot fi conținute chiar în noduri, sau nodurile pot conține doar legături către elementele respective, ca în figura 5.
Operațiile asupra listelor dublu înlănțuite sunt aceleași ca în cazul listelor simplu înlănțuite. Deosebirea constă în faptul că, la punerea sau eliminarea unui element, trebuie modificate mai multe legături. Complexitatea acestor operații este, de asemenea, aceeași ca la listele simplu înlănțuite.
- Figura 6 -
Poate exista și lista circulară dublu înlănțuită, care poate fi parcursă ciclic în ambele sensuri. Aceasta se obține din lista dublu înlănțuită, la care se adaugă atât o legătură de la ultimul nod către primul, cât și una de la primul nod către ultimul.