11.4. Lista dublu inlantuita (LDI)

2020/03/08 in Programare in C

Atat LSI, cat si LCSI conduc adesea la parcurgeri ineficiente ale lor. De exemplu, stergerea ultimului nod al unei LSI implica parcurgerea listei respective (vezi functia sun).

Astfel de parcurgeri pot fi uneori evitate folosind liste dublu inlantuite (LDI). Intr-o astfel de lista, fiecare nod contine doi pointeri:

• unul spre nodul urmator;
• unul spre nodul precedent.

In paragraful de fata vom presupune ca nodurile LDI au tipul definit ca mai jos:

typedef struct tnod {
   declaratii
   struct tnod *prec;
   struct tnod *urm;
} TNOD;

Pentru a gestiona o LDI vom utiliza variabilele globale prim si ultim, ca in cazul LSI.

Variabila prim pointeaza spre nodul pentru care prim -> prec = 0. Pentru restul nodurilor, pointerul prec al unui nod pointeaza spre nodul preecedent al listei.

Variabila ultim pointeaza spre un nod pentru care ultim -> urm = 0. Pentru restul nodurilor, pointerul urm al unui nod pointeaza spre nodul urmator al listei.

In concluzie, fiecare nod al listei are un nod precedent definit prin pointerul prec si un nod urmator definit prin pointerul urm.

O exceptie de la aceasta regula o constituie nodurile spre care pointeaza variabilele prim si ultim. Nodul spre care pointeaza prim nu are precedent, iar nodul spre care pointeaza ultim nu are urmator. Aceste noduri constituie capetele LDI.

In figura de mai jos se da o schema pentru listele dublu inlantuite:

In legatura cu LDI se pot defini aceleasi operatii ca si in cazul LSI:

1. crearea unei LDI;
2. accesul la un element al unei LDI;
3. inserarea unui nod intr-o LDI;
4. stergerea unui nod dintr-o LDI;
5. stergerea unei LDI;

11.4.1. Crearea unei LDI