Differenza tra matrici e liste collegate

Array vs Elenchi collegati

Array sono la struttura dei dati più comunemente utilizzati per memorizzare la raccolta di elementi. La maggior parte dei linguaggi di programmazione fornisce metodi per dichiarare facilmente gli array e gli elementi di accesso negli array. L'elenco collegato, più precisamente l'elenco collegato singolarmente, è anche una struttura di dati che può essere utilizzata per memorizzare la raccolta di elementi. È costituito da una sequenza di nodi e ogni nodo ha un riferimento al nodo successivo della sequenza.

Mostrato in figura 1, è un pezzo di codice tipicamente utilizzato per dichiarare e assegnare i valori ad una matrice. La Figura 2 illustra come una matrice sarebbe simile alla memoria.

Il codice sopra definisce un'array che può memorizzare 5 interi e si accede usando gli indici da 0 a 4. Una proprietà importante di una matrice è che l'intera matrice viene assegnata come un singolo blocco di memoria e ogni elemento ottiene il proprio spazio nel array. Una volta definita un'array, la sua dimensione è fissa. Quindi, se non siete sicuri circa la dimensione dell'array al tempo di compilazione, dovresti definire una matrice abbastanza grande da essere in sicurezza. Ma, per la maggior parte del tempo, usiamo in realtà meno numero di elementi di quanto abbiamo assegnato. Così una notevole quantità di memoria è in realtà sprecata. D'altra parte, se la "matrice abbastanza grande" non è in realtà abbastanza grande, il programma si bloccherà.

Un elenco collegato assegna la memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura complessiva viene ottenuta collegando questi elementi come collegamenti in una catena. Ogni elemento in un elenco collegato ha due campi come mostrato in Figura 3. Il campo dati contiene i dati effettivi memorizzati e il campo successivo contiene il riferimento all'elemento successivo della catena. Il primo elemento dell'elenco collegato viene memorizzato come testa dell'elenco collegato.

dati	successivo

Figura 3: Elemento di una lista collegata

La figura 4 rappresenta un elenco collegato con tre elementi. Ogni elemento memorizza i suoi dati e tutti gli elementi tranne l'ultimo memorizzano un riferimento all'elemento successivo. L'ultimo elemento ha un valore nullo nel suo campo successivo. È possibile accedere a qualsiasi elemento dell'elenco partendo dalla testa e seguendo il puntatore successivo fino a quando non si incontra l'elemento richiesto.

Anche se gli array e gli elenchi collegati sono simili nel senso che entrambi sono utilizzati per memorizzare la raccolta di elementi, presentano differenze a causa delle strategie che utilizzano per allocare la memoria ai suoi elementi. Le matrici allocano la memoria a tutti i suoi elementi come blocco singolo e la dimensione dell'array deve essere determinata in fase di runtime. Ciò renderebbe gli array inefficienti in situazioni in cui non si conosce la dimensione dell'array al momento della compilazione. Poiché un elenco collegato assegna la memoria ai suoi elementi separatamente, sarebbe molto efficiente in situazioni in cui non si conosce la dimensione dell'elenco alla volta di compilazione.Dichiarazione e accesso di elementi in un elenco collegato non sarebbe in linea diretta rispetto a come si accede direttamente agli elementi di un array utilizzando i suoi indici.