Matrice vs Liste legate
Tablourile sunt structura de date cea mai frecvent utilizată pentru stocarea colecției de elemente. Majoritatea limbajelor de programare oferă metode pentru a declara cu ușurință tablouri și a accesa elementele din tablouri. Lista legată, mai precis lista legată individual, este, de asemenea, o structură de date care poate fi utilizată pentru a stoca colecția de elemente. Este alcătuit dintr-o secvență de noduri și fiecare nod are o referință la următorul nod din secvență.
Afișat în figura 1, este o bucată de cod utilizată de obicei pentru a declara și atribui valori unei matrice. Figura 2 descrie cum ar arăta o matrice în memorie.
Codul de mai sus definește o matrice care poate stoca 5 numere întregi și sunt accesate folosind indici de la 0 la 4. O proprietate importantă a matricei este aceea că întreaga matrice este alocată ca un singur bloc de memorie și fiecare element primește propriul spațiu în matrice. Odată ce o matrice este definită, dimensiunea sa este fixă. Deci, dacă nu sunteți sigur de dimensiunea matricei la momentul compilării, va trebui să definiți o matrice suficient de mare pentru a fi în partea sigură. Dar, de cele mai multe ori vom folosi de fapt un număr mai mic de elemente decât le-am alocat. Deci, o cantitate considerabilă de memorie este de fapt irosită. Pe de altă parte, dacă „matricea suficient de mare” nu este de fapt suficient de mare, programul s-ar bloca.
O listă legată alocă memoria elementelor sale separat în propriul bloc de memorie și structura generală este obținută prin legarea acestor elemente ca verigi într-un lanț. Fiecare element dintr-o listă legată are două câmpuri așa cum se arată în Figura 3. Câmpul de date conține datele reale stocate, iar câmpul următor conține referința la următorul element din lanț. Primul element al listei conectate este stocat ca cap al listei conectate.
Figura 3: Elementul unei liste conectate
Figura 4 prezintă o listă legată cu trei elemente. Fiecare element își stochează datele și toate elementele, cu excepția ultimului, stochează o referință la următorul element. Ultimul element deține o valoare nulă în câmpul următor. Orice element din listă poate fi accesat începând de la cap și urmând următorul indicator până când îndepliniți elementul cerut.
Chiar dacă matricile și listele legate sunt similare în sensul că ambele sunt utilizate pentru a stoca colecția de elemente, acestea apar diferențe datorită strategiilor pe care le folosesc pentru a aloca memoria elementelor sale. Tablourile alocă memorie tuturor elementelor sale ca un singur bloc și dimensiunea tabloului trebuie să fie determinată la runtime. Acest lucru ar face matricile ineficiente în situații în care nu știți dimensiunea matricei la momentul compilării. Deoarece o listă legată alocă memorie elementelor sale separat, ar fi mult mai eficientă în situații în care nu cunoașteți dimensiunea listei la momentul compilării. Declarația și accesarea elementelor dintr-o listă legată nu ar fi simple în comparație cu modul în care accesați direct elementele dintr-o matrice folosind indicii săi.
