Liste inlantuite

Listele implementate ca tablouri prezinta desavantajul ca este necesar sa se impuna la construirea listei capacitatea acesteia, adica numarul maxim de elemente din lista. Este adevarat ca, in cazul claselor ArrayList si Vector din pachetul java.util acest desavantaj a fost evitat prin alocarea unui tablou de lungime mai mare in caz de depasire a capacitatii, dar aceasta necesita timp de calcul suplimentar pentru copiere. Listele inlantuite inlatura acest desavantaj, permitand in orice moment adaugarea de noi elemente sau eliminarea elementelor existente. Singura limitare a numarului de elemente din lista este capacitatea de memorie disponibila.

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.
 

Lista simplu inlantuita

Lista simplu inlantuita este o lista in fiecare nod contine o legatura catre elementul urmator ( figura 1) .


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


- Figura 2 -

Adaugarea s-a facut in urmatoarea ordine:
    - s-a creat un nou nod, caruia i-a fost atasat elementul corespunzator X (culoarea rosie);
    - s-a pus in nodul nou creat X o legatura catre nodul A care a fost anterior in capul listei, dupa care s-a pus drept cap al listei o legatura catre nodul adaugat X (legaturile cu culoare verde).

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


- Figura 3 -

In figura 4 este ilustrata inserarea unui element intr-o lista. 


-Figura 4 -

Inserarea se face astfel:
  - se construieste noul nod si i se adauga legatura catre obiectul continut (culoare rosie);
  - pornind de la primul nod, se parcurge lista pana se ajunge la nodul in fata caruia se face inserarea (in cazul de fata, cel care contine elementul C);
  - se se pun legaturile de la nodul precedent catre cel nou si de la acesta catre nodul urmator (culoare verde).
Parcurgerea listei pana la locul de inserare necesita, in medie, un numar de pasi proportional cu lungimea listei, deci complexitatea este O(n).

Actiunile de eliminare ale elementelor din lista sunt inverse celor prezentate mai sus si sunt echivalente cu ele in ce priveste complexitatea.

Lista dublu inlantuita

Lista dublu inlantuita este o lista, in care fiecare nod are doua legaturi: una catre nodul precedent si una catre nodul urmator (fig. 5). In consecinta, lista poate fi parcursa in ambele sensuri: de la cap la coada si de la coada la cap.


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

Lista circulara

Lista circulara se aseamana cu lista simplu inlantuita, cu deosebirea ca ultimul nod contine o legatura catre primul nod (trasata cu rosu in figura 6). In consecinta, lista poate fi parcursa in mod perpetuu, ceeace poate constitui un avantaj in anumite aplicatii.


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



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati