Liste înlănțuite

Listele implementate ca tablouri prezintă desavantajul că este necesar să se impună la construirea listei capacitatea acesteia, adică numărul maxim de elemente din listă. Este adevarat că, în cazul claselor ArrayList și Vector din pachetul java.util, acest desavantaj a fost evitat prin alocarea unui tablou de lungime mai mare în caz de depășire a capacității, dar aceasta necesita timp de calcul suplimentar pentru copiere. Listele înlănțuite înlătură acest desavantaj, permițând în orice moment adăugarea de noi elemente sau eliminarea elementelor existente. Singura limitare a numărului de elemente din lista înlănțuită este capacitatea de memorie disponibilă.

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.
 

Lista simplu înlănțuită

Lista simplu înlănțuită este o listă care în fiecare nod conține o legatură către elementul următor ( figura 1) .


- 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.


- Figura 2 -

Adăugarea s-a făcut în urmatoarea ordine:
    - s-a creat un nou nod, căruia i-a fost atașat elementul nou adăugat  X (culoarea rosie);
    - s-a pus în nodul nou creat X o legatură către nodul A care a fost anterior în capul listei, după care s-a pus drept cap al listei o legatura către nodul adaugat X (legaturile cu culoare verde).

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).


- Figura 3 -

În figura 4 este ilustrată înserarea unui element într-o listă. 


-Figura 4 -

Înserarea se face astfel:
  - se construiește noul nod și i se adaugă legătura către obiectul conținut (culoare roșie);
  - pornind de la primul nod, se parcurge lista pâna se ajunge la nodul în fața căruia se face înserarea (în cazul de față, cel care contine elementul C);
  - se se pun legăturile de la nodul precedent către cel nou și de la acesta către nodul următor (culoare verde).
Parcurgerea listei până la locul de înserare necesită, în medie, un număr de pași proporțional cu lungimea listei, deci complexitatea este O(n).

Acțiunile de eliminare a elementelor din listă sunt inverse celor prezentate mai sus și sunt echivalente cu ele în ce privește complexitatea.

Lista dublu înlănțuită

Lista dublu înlănțuită este o listă, în care fiecare nod are două legături: una către nodul precedent și una către nodul următor (fig. 5). În consecință, lista poate fi parcursă în ambele sensuri: de la cap la coadă și de la coadă la cap.


- 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.

Lista circulară

Lista circulară se aseamănă cu lista simplu înlănțuită, cu deosebirea că ultimul nod conține o legătură către primul nod (trasată cu roșu în figura 6). În consecință, lista poate fi parcursă în mod perpetuu, ceeace poate constitui un avantaj în anumite aplicații.


- 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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați