Liste liniare alocate dublu inlantuit

Motivul pentru care acestea se numesc dublu inlantuit este faptul ca nodurile care le compun au 2 campuri care pointeaza spre acelasi tip. Astfel, o lista alocata dublu inlantuit este o structura de date de forma:

. .

x1 x2 x3 xn

x1, x2, . , xn fiind nodurile listei. Campul st al primului element precum si campul dr al ultimului element trebuie sa fie NULL, deoarece nimic nu pointeaza spre primul element si ultimul element nu pointeaza spre nimic.

Nodurile listei sunt definite astfel:

struct nod

nod *A,*B,*C;

Avantajul utilizarii listei alocate dublu inlantuit este dat de faptul ca o astfel de lista poate fi parcursa in ambele sensuri.

Operatiile ce se pot efectua asupra unei liste liniare alocate dublu inlantuit sunt asemanatoare cu cele de la listele liniare alocate simplu inlantuit, singura diferenta fiind aceea ca legaturile dintre noduri trebuie facute in dublu sens.

De exemplu:

Presupunem ca avem de sters nodul B din lista de mai jos.

A B C

Deci, trebuie sa il conectam pe nodul A la nodul C.

A->dr = C;

C->st = A;

Dupa acest set de instructiuni, lista va arata in felul urmator:

A B C

Apoi stergem nodul B, utilizand functia delete.

Presupunem ca trebuie sa adaugam nodul C intre nodurile A si B. Initial, lista arata astfel:

A B

Intai, il creem pe C:

C = new nod;

A B

C

Pentru a-l insera pe C intre A si B, trebuie sa il legam pe A la C si pe C la B:

A->dr=C;

C->st=A;

B->st=C;

C->dr=B;

Astfel, am obtinut secventa dorita:

A B C

Liste circulare alocate simplu si dublu inlantuit

Acestea sunt similare cu listele liniare alocate simplu si dublu inlantuit, numai ca ultimul element pointeaza catre primul (si primul catre ultimul, in cazul celor dublu inlantuit).

O lista circular simplu inlantuita are urmatoarea forma: