Link.RO
11. Liste
2020/02/21 in Programare in C
Lista este o multime dinamica, intelegand prin aceasta ca are un numar variabil de elemente. La inceput, lista este o multime vida. In procesul executiei programului se pot adauga elemente noi listei si totodata pot fi eliminate diferite elemente din lista, de care nu mai este nevoie.
Elementele unei liste sunt date de acelasi tip. In forma cea mai generala, tipul comun elementelor unei liste este un tip utilizator. Deci, elementele unei liste sunt structuri de acelasi tip. Acest fapt ne conduce la ideea de a organiza o lista sub forma de tablou. Acest lucru este posibil, dar de obicei nu este eficient, deoarece lista are o natura dinamica, ori tablourile in limbajul C nu sunt dinamice. La compilare este necesar sa se defineasca un maxim pentru numarul elementelor unui astfel de tablou, maxim care uneori nu se poate stabili dinainte. Se poate adopta o solutie de compromis daca se pastreaza elementele listei in memoria heap, iar intr-o memorie statica sau pe stiva se aloca un tablou de pointeri spre elementele listei. In acest caz, elementele tabloului de pointeri ocupa fiecare 16 biti sau 32 de biti daca pointerii respectivi sunt de tip far. Tabloul de pointeri se va dimensiona la un numar de elemente suficient de mare. Avantajul pastrarii elementelor listei in memoria heap rezulta din faptul ca supradimensionarea tabloului de pointeri nu conduce la un consum prea mare de memorie deoarece elementele tabloului sunt pointeri si nu insasi elementele listei. In acelasi timp, memoria heap este gestionata optim, deoarece ea contine, in fiecare moment al executiei programului, numai elementele necesare din lista. Cu toate acestea, exista situatii in care este dificil a evalua numarul maxim al elementelor unei liste, precum si cazuri cand numarul lor difera mult de la o executie la alta. De aceea, apare problema de a organiza altfel multimile de tip lista. Se obisnuieste sa se ordoneze elementele unei liste folosind pointeri care intra in compunerea elementelor listei. Datorita acestor pointeri, elementele unei liste devin structuri recursive. Listele organizate in acest fel se numesc liste inlantuite.
In concluzie, o multime dinamica de structuri recursive de acelasi tip, pentru care sunt definite una sau mai multe relatii de ordine cu ajutorul unor pointeri din compunerea structurilor respective, se numeste lista inlantuita.
De obicei, elementele unei liste se numesc noduri.
Daca intre nodurile unei liste exista o singura relatie de ordine, atunci lista se numeste simplu inlantuita. In mod analog, lista este dublu inlantuita daca intre nodurile ei sunt definite doua relatii de ordine.
In general, vom spune ca o lista este n-inlantuita daca intre nodurile ei sunt definite n relatii de ordine.
In legatura cu listele inlantuite se au in vedere unele operatii de interes general:
- crearea unei liste inlantuite;
- accesul la un nod oarecare al unei liste inlantuite;
- inserarea unui nod intr-o lista inlantuita;
- stergerea unui nod intr-o lista inlantuita;
- stergerea unei liste inlantuite.