Introducere in Stiinta Calculatoarelor 2013 | Page 60

Alte operaţii pot fi:
 parcurgerea listei în scopul căutării unui nod (de indice sau
valoare cunoscută), al primului sau ultimului element (capul sau
coada listei);
 determinarea elementului succesor sau predecesor pentru un nod
dat;
 iniţializarea listei – adică ştergerea tuturor elementelor din listă
(vidarea listei).
Operaţiile de ştergere ale unui nod sau a întregii liste face totodată
eliberarea zonei de memorie ocupată, spre a fi utilizată pentru alte
variabile dinamice.
Tipuri de liste
Dacă pointer-ul ultimului nod En al listei indică primul element E1,
atunci lista se numeşte listă circulară, fiindcă parcurgerea liste se poate
face până la capăt şi apoi din nou de la început. Parcurgerea listei se
face prin „saltul” între indicatori (P0, P1, ..., Pi, ...) iar vizitarea nodului
i se face prin prelucrarea (sau pur şi simplu consultarea) valorii Ei.
Fiindcă lista simplu înlănţuită nu poate fi parcursă decât de la „cap” (P0)
la „coadă” (Pn) iar pentru revenirea către cap trebuie reluată parcurgerea
de la cap, se foloseşte adesea lista dublu înlănţuită; aceasta prezintă
două câmpuri indicator: unul spre dreapta (spre coadă) altul spre stânga
(spre cap). Parcurgerea listei se poate face uşor în ambele sensuri prin
„salturi” atât spre dreapta cât şi spre stânga.
Cozi – numite şi liste FIFO („First În First Out” – primul intrat primul
ieşit) sunt liste la care interesează în special cele două capete şi
modurile cum se adaugă noi elemente sau se elimină elementele - pentru
aceste tipuri de liste introducerea / eliminarea de elemente se face doar
prin capete.
Stive – numite şi liste LIFO („Last În First Out” – ultimul intrat primul
ieşit) – care seamănă cu un pachet de cărţi de joc: adăugarea de noi
elemente se face prin capătul de sus (vârful stivei) iar eliminarea la fel.
Acest tip de listă este util pentru cazurile când prelucrările parcurg
datele într-un sens iar apoi le parcurg în sens invers.
60