Matrice vs liste conectate
Matricele sunt cea mai folosită structură de date pentru a stoca colecția de elemente. Majoritatea limbajelor de programare oferă metode pentru a declara cu ușurință matrice și a accesa elementele din matrice. Lista legată, mai precis lista cu legături unice, este, de asemenea, o structură de date care poate fi folosită pentru a stoca o colecție 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 folosită de obicei pentru a declara și a atribui valori unui tablou. Figura 2 ilustrează cum ar arăta o matrice în memorie.
Codul de mai sus definește o matrice care poate stoca 5 numere întregi și acestea sunt accesate folosind indici de la 0 la 4. O proprietate importantă a unei matrice este 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 în momentul compilării, ar trebui să definiți o matrice suficient de mare pentru a fi în partea de siguranță. Dar, de cele mai multe ori vom folosi de fapt un număr mai mic de elemente decât 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 se va prăbuși.
O listă legată alocă memoria elementelor sale separat în propriul bloc de memorie, iar 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.
| date | următorul |
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 pornind de la cap și urmând indicatorul următor până când întâlniți elementul necesar.
Chiar dacă matricele și listele legate sunt similare în sensul că ambele sunt folosite pentru a stoca colecția de elemente, ele apar diferențe din cauza strategiilor pe care le folosesc pentru a aloca memorie elementelor sale. Array-urile alocă memorie tuturor elementelor sale ca un singur bloc, iar dimensiunea matricei trebuie determinată în timpul execuției. Acest lucru ar face ca tablourile să fie ineficiente în situațiile în care nu cunoașteți dimensiunea matricei la momentul compilării. Deoarece o listă legată alocă memorie elementelor sale separat, ar fi mult eficient în situațiile în care nu cunoașteți dimensiunea listei în momentul compilării. Declararea și accesarea elementelor dintr-o listă conectată nu ar fi simplă în comparație cu modul în care accesați direct elementele dintr-o matrice folosind indicii acesteia.
