Candale Silviu (silviu) Lista liniară este o structură de date logică, cu date omogene, în care fiecare element are exact un element predecesor și exact un element succesor, cu excepția primului și al ultimului element.
Elementele unei liste se mai numesc noduri. Lungimea unei liste reprezintă numărul de noduri din listă. O lista care nu are niciun element se numește listă vidă.
Asupra listei se pot executa anumite operații:
- inițializarea listei – crearea unei liste vide;
- crearea listei – adăugarea repetată a unor elemente, pornind de la o listă vidă;
- inserarea unui element în listă – la început, la sfârșit, în interior;
- ștergerea unui element din listă – de la început, de la sfârșit, din interior;
- parcurgerea listei – analizarea elementelor listei, pentru a obține anumite informații despre ele;
- căutarea unui element într-o listă;
- concatenarea a două liste, divizarea unei liste.
O modalitate deja cunoscută de implementare a listelor este prin intermediul tablourilor statice, obținându-se astfel liste liniare secvențiale. Tablourile au fost studiate deja, precum și operațiile amintite mai sus; ele au o serie de avantaje care trebuie reținute:
- accesul la un anumit element se face prin indicele acestuia și este foarte rapid;
- tablourile sunt zone contigue de memorie – elementele sunt alocate în memorie în zone învecinate;
- elementele listei conțin numai informațiile utile.
Ele au și o serie de dezavantaje:
- operațiile de inserare și ștergere a elementelor presupun parcurgerea tabloului, ceea ce duce la algoritmi lenți;
- dimensiunea tablourilor (numărul de elemente) este precizat la compilare, iar la execuție pot să apară următoarele situații:
- spațiul alocat pentru tablou poate fi insuficient;
- spațiul alocat pentru tablou poate fi mult mai mare decât este necesar.
O altă modalitate de implementare a listelor este sub forma listelor liniare alocate dinamic. În acest caz, fiecare element al listei este o variabilă dinamică; aceasta va conține, pe lângă informația utilă și informația de legătură, adică adresa elementului succesor și, eventual, adresa elementului precedent. Sigur, aceste adrese vor fi memorate prin intermediul pointerilor.
Dacă un nod al listei conține, alături de informația utilă, doar adresa următorului element, avem o listă alocată dinamic simplu înlănțuită; pentru a gestiona o asemenea listă trebuie să cunoaștem adresa primului element al listei. Următoarele elementele vor fi descoperite succesiv, elementul curent conținând ca informație de legătură adresa următorului element.
Dacă un nod al listei conține, alături de informația utilă, atât adresa elementului următor, cât și a celui precedent, avem o listă liniară dublu înlănțuită; de regulă cunoaștem adresa primului și/sau a ultimului element, dar pentru a gestiona o asemenea listă este suficient să cunoaștem adresa unui element oarecare a acesteia. Pornind de la acesta pot fi determinate primul și ultimul element al listei.