LISTA DUBLU INLANTUITA

Lista dublu inlantuita

Lista dublu inlantuita este formata din noduri care contin:

informatie

adresa urmatorului nod

adresa precedentului nod

Avantajul utilizarii listelor dublu inlantuite rezulta din posibilitatea parcurgerii (traversarii) listei in ambele sensuri: de la primul la ultimul, respectiv, de la ultimul la primul nod. Acest lucru permite o manipulare mai flexibila a nodurilor listei

Structura unui nod al listei dublu inlantuite este urmatoarea:

struct nod

In exemplele urmatoare vom utiliza un tip de date utilizator prin care specificam tipul nodurilor listei:

typedef struct nod

tnod;

Ca si la lista simplu inlantuita, principalele operatii sunt:

crearea;

accesul la un nod; parcurgerea listei

adaugarea unui nod;

stergerea unui nod,

stergerea listei.

Gestionarea unei liste dublu inlantuite se face in maniera similara listelor simplu inlantuite prin adresele nodurilor prim si ultim. In plus, nodul prim se marcheaza prin stabilirea adresei precedentului sau la Null: prim->prec=0.

tnod *prim,*ultim;

Figura urmatoare sugereaza maniera de organizare a unei liste dublu inlantuite (alocate dinamic):

Crearea listei dublu inlantuita

Crearea listei vide presupune initializarea celor doi pointer de control prim si ultim cu valoarea 0 (Null): prim=ultim=0. Crearea unei liste cu mai mult de un nod se rezuma la apelul repetat al subrutinelor de adaugare a unui nou nod (inaintea primului sau dupa ultimul nod).

Functia urmatoare este un exemplu prin care se poate crea o lista dublu inlantuita prin adaugarea noilor noduri dupa ultimul nod. Un caz particular al procedurii de adaugare a noului nod este tratat distinct: in situatia in care lista este vida, dupa adaugarea unui nod trebuie marcate nodurile prim si ultim. Functia incarca_nod este cea definita in capitolul dedicat listelor simplu inlantuite.

else

printf('nIntroduceti? (1/0)');scanf('%d',&rasp);

}

Parcurgerea listei dublu inlantuita

Spre deosebire de listele simplu inlantuite, listele dublu inlantuite pot fi parcurse in ambele sensuri. Prezentam in continuare functii de afisare a informatiei nodurilor parcurse in doua variante: prin folosirea legaturii urmator (urm), respectiv, succesor (prec).

ADAUGAREA UNUI NOU NOD

Sunt tratate in continuare diferite modalitati de adaugare a unui nou nod intr-o lista dublu inlantuita:

Adaugare inaintea primului nod

Adaugarea unui nou nod inaintea primului nod ale listei presupune efectuarea urmatoarelor operatii:

alocarea si incarcarea noului nod:

stabilirea faptului ca acest nou nod va adresa ca urmator element chiar pe nodul prim: nou->urm=prim (1)

stabilirea faptului ca nodul prim va referi ca precedent element pe nodul nou: prim->prec=nou (2)

stabilirea noului nod ca prim element al listei: prim=nou (3)

marcarea nodului prim: prim->prec=0 (4)

Observatie: In cazul in care lista este inaintea adaugarii unui nod nou, efectul operatiei consta in obtinerea unei liste cu un singur element, fapt pentru care capetelor listei prim si ultim sunt confundate si este necesara tratarea acestui caz particular.

else

Adaugare dupa ultimul nod

Adaugarea unui nou nod dupa ultimul nod al listei presupune efectuarea urmatoarelor operatii:

alocarea si incarcarea noului nod:

stabilirea faptului ca acest nou nod va adresa ca precedent element chiar pe nodul ultim: nou->prec=ultim (1)

stabilirea faptului ca nodul ultim va referi ca urmator element pe nodul nou: ultim->urm=nou (2)

stabilirea noului nod ca ultim element al listei: ultim=nou (3)

marcarea nodului ultim: ultim->urm=0 (4)

Cazul special al procedurii (lista este vida) se trateaza in mod diferit.

else

Adaugare inaintea uni nod specificat prin cheie

Adaugarea unui nod inaintea unui nod specificat prin valoarea cheii, se realizeaza prin doua etape:

cautarea nodului inaintea caruia se va face inserarea

inserarea propriu-zisa

Reamintim ca la operatia similara pentru liste simplu inlantuite era necesara determinarea nodului precedent nodului precizat de cheie li acest lucru se realiza printr-un pointer auxiliar in care se retinea acea adresa. In cazul listelor dublu inlantuite lucrurile sunt simplificate datorita adreselor precedent continute de fiecare nod, adrese utile in accesarea vecinilor (nodurile anterioare).

Daca nodul cautat este chiar primul, problema se reduce la un caz particular tratat prin functia adaugare_prim. Daca lista este vida sau nodul cautat nu s-a gasit, nu se va adauga un nou nod.

else

else

}

}

Observatie: Pentru manevrarea legaturii urmatoare a nodului precedent celui curent (notam nodul curent p) este valabila constructia: (p->pre)->urm, unde (p->pre) este adresa precedentului nodului p.

Adaugare dupa un nod specificat prin cheie

Procedura de adaugare a unui nou nod dupa un nod precizat prin valoarea cheii este simalra celei prezentate la punctul 3. Cazul particular este cel in care nodul cautat este ultimul nod al listei, in aceasta situatie se va apela functia adaugare_ultim.    Daca lista este vida sau nu s-a gasit nodul cautat, nu are sens sa se opereze adaugarea unui nou nod.

Inserarea propriu-zisa a nodului nou inaintea nodului p presupune refacerea legaturilor in asa fel incat consistenta listei sa fie asigurata (sa nu se piarda secvente de noduri prin distrugerea accesului la ele ):

nodul nou va avea ca legatura urm pe urmatorul nod al nodului p:

nou->urm=p->urm; (1)

nodul p va fi urmat de nou

p->urm=nou; (2)

precedentul nodului nou va fi nodul p

nou->pre=p; (3)

nodul precedent al nodului urmatorul lui p devine nou:

(p->urm)->pre=nou; (4)

else

else

}

}

STERGEREA UNUI NOD

Stergerea capetelor prim si ultim ale unei liste dublu inlantuite nu difera prin costul de calcul precum la listele simplu inlantuite. Am vazul ca in cazul listelor simplu inlantuite stergerea ultimului nod necesita un efort computational mai mare. Prin legatura prec a nodurilor unei liste dublu inlantuite putem accesa nodurile precedent, fapt pentru care, la stergerea ultimului nod nu este necesara traversarea completa a listei.

Stergerea unui capat al listei presupune:

salvarea temporara a adresei capatului respectiv intr-un pointer auxiliar

actualizarea si marcarea noului capat

eliberarea memoriei

Oferim in continuare doua variante pentru functiile de stergere a capetelor prim si ultim:

Stergerea unui nod oarecare

Stergerea unui nod oarecare precizat prin valoarea cheii presupune:

cautarea nodului

stergerea propriu-zisa a nodului

Cautarea nodului se face prin parcurgerea intr-un sens a listei si compararea valorii cheii nodurilor curente cu valoarea data. Daca se gaseste un nod care verifica conditie, se va opera etapa de stergere propriu-zisa a nodului prin:

o        salvarea adresei nodului de sters

o        refacerea legaturilor pentru a asigura consistenta listei si posibilitatea parcurgerii ulterioare in ambele sensuri

o        eliberarea memoriei alocate nodului de sters

Refacerea legaturilor consta din urmatoarele asignari:

precedentul urmatorului lui p devine precedentul lui p

p->urm->pre=p->pre; (1)

urmatorul precedentului lui p devine urmatorul lui p:

p->pre->urm=p->urm; (2)

Cazurile particulare se trateaza separat: lista este deja vida sau lista devine vida dupa stergerea nodului.

p=prim;

while(p!=0)

if (p==ultim)

pvechi=p; //salvare adresa nod curent

p->urm->pre=p->pre; (1)

p->pre->urm=p->urm; (2)

free(pvechi); //eliberare memoriei- adresa pvechi

return;

}

else //nu s-a gasit inca

p=p->urm; //trecere la urmatorul nod

}

Stergerea listei

Stergerea completa listei dublu inlantuita se poate face cu acelasi efort de calcul prin apelarea repetata a functiei stergere_prim sau stergere_ultim. Stergerea capetelor listei nu asigura eliberarea memoriei ocupate de nodurile intermediare.

Exemplu:stergerea listei prin apelul repetat al functiei de stergere a primului nod.