Array vs elenchi collegati
Gli array sono la struttura dati più comunemente utilizzata per memorizzare la raccolta di elementi. La maggior parte dei linguaggi di programmazione fornisce metodi per dichiarare facilmente gli array e accedere agli elementi negli array. L'elenco collegato, più precisamente un 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 nella sequenza.
Nella figura 1 è mostrato un pezzo di codice tipicamente utilizzato per dichiarare e assegnare valori a un array. La Figura 2 mostra come apparirebbe un array nella memoria.
Il codice sopra definisce un array che può memorizzare 5 numeri interi e vi 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 nell'array. Una volta definito un array, la sua dimensione viene fissata. Quindi, se non sei sicuro della dimensione dell'array in fase di compilazione, dovresti definire un array abbastanza grande da essere al sicuro. Ma la maggior parte delle volte utilizzeremo effettivamente un numero di elementi inferiore a quello che abbiamo assegnato. Quindi una notevole quantità di memoria viene effettivamente sprecata. D'altra parte, se la "matrice abbastanza grande" non è effettivamente abbastanza grande, il programma andrebbe in crash.
Una lista concatenata alloca la memoria ai propri elementi separatamente nel proprio blocco di memoria e la struttura complessiva si ottiene collegando questi elementi come collegamenti in una catena. Ogni elemento in un elenco collegato ha due campi, come mostrato nella 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 inizio dell'elenco collegato.
Figura 3: elemento di un elenco collegato
La Figura 4 mostra un elenco collegato con tre elementi. Ogni elemento memorizza i propri 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 nell'elenco iniziando dalla testa e seguendo il puntatore successivo fino a incontrare l'elemento richiesto.
Anche se gli array e gli elenchi collegati sono simili nel senso che entrambi vengono utilizzati per memorizzare la raccolta di elementi, subiscono differenze a causa delle strategie che utilizzano per allocare la memoria ai suoi elementi. Gli array allocano la memoria a tutti i suoi elementi come un singolo blocco 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 la 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 al modo in cui si accede direttamente agli elementi in un array utilizzando i suoi indici.
