Array vs Liste collegate
Gli array sono la struttura di dati più comunemente utilizzata per memorizzare la raccolta di elementi. La maggior parte dei linguaggi di programmazione fornisce metodi per dichiarare facilmente array e accedere agli elementi negli array. L'elenco collegato, più precisamente l'elenco con collegamenti singoli, è anche una struttura di dati che può essere utilizzata per memorizzare raccolte di elementi. È composto da una sequenza di nodi e ogni nodo ha un riferimento al nodo successivo nella sequenza.
Mostrato nella figura 1, è un pezzo di codice tipicamente utilizzato per dichiarare e assegnare valori a un array. La figura 2 mostra come apparirà un array nella memoria.
Il codice sopra definisce un array che può memorizzare 5 numeri interi a cui si accede utilizzando gli indici da 0 a 4. Una proprietà importante di un array è che l'intero array è allocato come un singolo blocco di memoria e ogni elemento ottiene il proprio spazio nella matrice. Una volta definita una matrice, la sua dimensione viene fissata. Quindi, se non sei sicuro della dimensione dell'array in fase di compilazione, dovresti definire un array sufficientemente grande per essere al sicuro. Ma la maggior parte delle volte utilizzeremo effettivamente un numero di elementi inferiore a quello che abbiamo allocato. Quindi una notevole quantità di memoria viene effettivamente sprecata. D' altra parte, se "array abbastanza grande" non è effettivamente abbastanza grande, il programma andrebbe in crash.
Una lista concatenata alloca memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura complessiva si ottiene collegando questi elementi come anelli di una catena. Ciascun elemento in un elenco collegato ha due campi, come mostrato nella Figura 3. Il campo dati contiene i dati effettivamente archiviati e il campo successivo contiene il riferimento all'elemento successivo nella catena. Il primo elemento dell'elenco collegato viene memorizzato come capo dell'elenco collegato.
| dati | successivo |
Figura 3: Elemento di un elenco collegato
La figura 4 mostra 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 contiene un valore nullo nel campo successivo. È possibile accedere a qualsiasi elemento dell'elenco partendo dall'inizio e seguendo il puntatore successivo fino a raggiungere l'elemento richiesto.
Anche se gli array e le liste collegate sono simili nel senso che entrambi sono usati per memorizzare raccolte di elementi, subiscono differenze dovute alle strategie che usano per allocare memoria ai suoi elementi. Gli array allocano memoria a tutti i suoi elementi come un blocco singolo e la dimensione dell'array deve essere determinata in fase di esecuzione. Ciò renderebbe gli array inefficienti in situazioni in cui non si conosce la dimensione dell'array in fase di compilazione. Poiché un elenco collegato alloca memoria ai suoi elementi separatamente, sarebbe molto efficiente in situazioni in cui non si conosce la dimensione dell'elenco in fase di compilazione. La dichiarazione e l'accesso agli elementi in un elenco collegato non sarebbero semplici rispetto a come si accede direttamente agli elementi in un array utilizzando i suoi indici.
