Liste - Lista simplu si dublu inlantuite

Liste

Cea mai simpla lista, lista liniara, arata astfel:

Lista este o multime dinamica, intelegand prin aceasta faptul ca ea are un numar variabil de elemente. De remarcat diferentele fata de definitia tabloului: tabloul este o strucutra statica, in care toate elementele sunt de acelasi tip insa numarul de elemente este constant.

La inceput lista este o multime vida. In procesul executiei a programului se pot adauga elemente noi listei si totodata pot fi eliminate diferite elemente din lista.

Elementele (componentele) unei liste sunt structuri de acelasi tip si se numesc noduri sau inregistrari. Numarul de noduri se numeste lungimea listei.

Inregistrarile unei liste trebuie sa contina cel putin doua campuri:

un camp informational - retine informatiile

un camp tip pointer - retine adrese

Structura corespunzatoare de date trebuie sa ne permita sa determinam eficient care este primul/ultimul nod in structura si care este predecesorul/succesorul (daca exista) unui nod dat.

O lista este n-inlantuita daca intre nodurile ei sunt definite n relatii de ordine.

Implementarea unei liste se poate face in principal in doua moduri:

Implementarea secventiala, in locatii succesive de memorie, conform ordinii nodurilor in lista. Avantajele acestei tehnici sunt accesul rapid la predecesorul /succesorul unui nod si gasirea rapida a primului/ultimului nod. Dezavantajele sunt inserarea/stergerea relativ complicata a unui nod si faptul ca, in general, nu se foloseste intreaga memorie alocata listei.

Implementarea inlantuita. In acest caz, fiecare nod contine doua parti: informatia propriu-zisa si adresa nodului succesor. Alocarea memoriei fiecarui nod se poate face in mod dinamic, in timpul rularii programului. Accesul la un nod necesita parcurgerea tuturor predecesorilor sai, ceea ce poate lua ceva mai mult timp. Inserarea / stergerea unui nod este in schimb foarte rapida. Se pot folosi doua adrese in loc de una, astfel incat un nod sa contina pe langa adresa nodului succesor, si adresa nodului predecesor. Obtinem astfel o lista dublu inlantuita, care poate fi traversata in ambele directii.

Desi listele sunt definite ca fiind multimi dinamice, implementarea listei inlantuita se poate face cel mai simplu prin tablouri. Acest, insa, nu este eficient (listele fiind dinamice).

Lista simplu inlantuita

Intre nodurile listei simplu inlantuite avem o singura relatie de ordonare. Exista un singur nod care nu mai are succesor si un singur nod care nu mai are predecesor. Aceste noduri formeaza capetele listei.

Lista se numeste simplu inlantuita deoarece fiecare nod, cu exceptia ultimului, retine adresa nodului urmator.

In continuare camp se va numi urm si are capacitatea de a retine adresa urmatoarei inregistrari din cadrul listei.

Liste dublu inlantuite

Listele dublu inlantuite apar din necesitatea traversarii unei liste si inainte si inapoi, deci a cunoasterii pentru un nod a succesorului si predecesorului sau.

Problema se rezolva prin pastrarea in campurile unui nod a unei referinte spre nodul anterior si a uneia spre cel succesor. Intr-o astfel de lista fiecare nod contine doi pointeri: unul spre nodul urmator si unul spre nodul precedent. Astfel fiecare nod al listei are un nod precedent definit prin pointerul prec si un nod urmator definit prin pointerul urm.

De aici denumirea de lista dublu inlantuita, descrisa astfel:

type pointer=^nod;
nod=record info:tip_info;
anterior,urmator:pointer
end;

Listele circulare se folosesc si in varianta in care se pastreaza o variabila pointer spre primul nod, ultimul avand inlantuirea nil, precum si in varianta circulara in care primul nod se inlantuie dublu cu ultimul;in varianta circulara, dispare notiunea de prim, ultim nod, existand doar un pointer ce indica un nod oarecare din lista, parcurgerea celorlalte putand fi facuta in oricare din cele doua sensuri.

Modelul listei dublu inlantuite, pentru care se vor da explicatiile in continuare, este prezentat in figura urmatoare.

Tipul unui nod dintr-o lista dublu inlantuita este definit astfel:

typedef struct tip_nod TIP_NOD;

Ca si la lista simplu inlantuita, principalele operatii sunt:

crearea;

accesul la un nod;

inserarea unui nod;

stergerea unui nod,

stergerea listei.

Lista dublu inlantuita va fi gestionata prin pointerii prim si ultim:

tip_nod *prim, *ultim;

prim -> prec = 0;

ultim -> urm = 0;

ultim = 0;