Diferența dintre matrice și listele asociate

Arrays vs. Liste legate

Arrays sunt structura de date cea mai frecvent utilizată pentru stocarea colecției de elemente. Cele mai multe limbi de programare oferă metode pentru a declara cu ușurință matrice și elemente de acces în matrice. O listă asociată, mai precis o listă cu un singur link, este, de asemenea, o structură de date care poate fi utilizată pentru stocarea colecției de elemente. Este alcătuită dintr-o secvență de noduri și fiecare nod are o referință la nodul următor din secvență.

Afișată în figura 1, este o bucată de cod utilizată în mod obișnuit pentru a declara și a atribui valori unei matrice. Figura 2 prezintă modul în care ar arăta o matrice în memorie.

Codul de mai sus definește un matrice care poate stoca 5 numere întregi și acestea sunt accesate folosind indicii 0 până la 4. O proprietate importantă a unei matrice este aceea că întregul matrice este alocat ca un singur bloc de memorie și fiecare element își are propriul spațiu în matrice. Odată ce o matrice este definită, dimensiunea acesteia 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 mai puține elemente decât ne-am alocat. Deci, o cantitate considerabilă de memorie este de fapt pierdută. Pe de altă parte, dacă "matricea suficientă" nu este destul de mare, programul s-ar prăbuși.

O listă legată alocă memoria elementelor sale separat în propriul bloc de memorie și structura globală este obținută prin legarea acestor elemente ca legături într-un lanț. Fiecare element dintr-o listă legată are două câmpuri, după cum se arată în Figura 3. Câmpul de date păstrează datele reale stocate, iar câmpul următor reține referința la următorul element din lanț. Primul element al listei legate este stocat ca capul listei legate.

Figura 3: Elementul unei liste asociate

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 elementul următor. 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 pointerul următor până când veți găsi elementul necesar.

Chiar dacă matricele și listele legate sunt similare în sensul că ambele sunt folosite pentru a stoca colectarea de elemente, acestea au diferențe datorită strategiilor pe care le folosesc pentru a aloca memoria elementelor sale. Arrays alocă memoria tuturor elementelor sale ca un singur bloc, iar mărimea matricei trebuie determinată la timpul de execuție. Acest lucru ar face ca matricele să fie ineficiente în situațiile în care nu cunoașteți dimensiunea matricei la momentul compilării. Deoarece o listă legată alocă memoria elementelor sale separat, ar fi mult mai eficientă în situațiile în care nu cunoașteți dimensiunea listei la momentul compilării. Declararea și accesarea elementelor dintr-o listă asociată nu ar fi directă în comparație cu modul în care accesați direct elementele dintr-un matrice utilizând indicii săi.