Differenza tra array e liste collegate

Array vs Liste collegate

Le matrici 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 matrici e accedere agli elementi 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 nella sequenza.

Nella figura 1 è mostrato un pezzo di codice utilizzato in genere per dichiarare e assegnare valori a un array. La Figura 2 mostra come apparirà una matrice nella memoria.

Il codice sopra definisce un array che può memorizzare 5 numeri interi e vi si accede usando 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 è fissa. Quindi, se non si è sicuri della dimensione dell'array in fase di compilazione, si dovrà definire una matrice abbastanza grande da essere nella parte sicura. Ma, nella maggior parte dei casi, useremo un numero di elementi inferiore a quello che abbiamo assegnato. Quindi una notevole quantità di memoria è effettivamente sprecata. D'altra parte se la "matrice abbastanza grande" non è effettivamente abbastanza grande, il programma si bloccherebbe.

Una lista collegata assegna la memoria ai suoi elementi separatamente nel proprio blocco di memoria e la struttura generale è ottenuta collegando questi elementi come collegamenti in una catena. Ogni elemento in una lista collegata 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 nella catena. Il primo elemento dell'elenco collegato è memorizzato come capo dell'elenco collegato.

Figura 3: elemento di una lista collegata

La Figura 4 mostra una lista collegata 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 suo campo successivo. È possibile accedere a qualsiasi elemento nella lista iniziando dalla testa e seguendo il puntatore successivo fino a quando non si incontra l'elemento richiesto.

Anche se gli array e le liste concatenate sono simili nel senso che entrambi vengono utilizzati per memorizzare la raccolta di elementi, presentano differenze a causa delle strategie che usano per allocare la memoria ai suoi elementi. Le matrici allocano la memoria a tutti i suoi elementi come un singolo blocco 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 in fase di compilazione. Poiché una lista collegata alloca separatamente la memoria ai suoi elementi, sarebbe molto efficace in situazioni in cui non si conosce la dimensione della lista in fase di compilazione. La dichiarazione e l'accesso agli elementi in un elenco collegato non sarebbero diretti rispetto al modo in cui si accede direttamente agli elementi in un array usando i suoi indici.