Gli array memorizzano gli elementi in posizioni di memoria contigue, risultando in indirizzi facilmente calcolabili per gli elementi memorizzati e questo permette un accesso più veloce ad un elemento ad un indice specifico. Le liste collegate sono meno rigide nella loro struttura di memorizzazione e gli elementi di solito non sono memorizzati in posizioni contigue, quindi hanno bisogno di essere memorizzati con tag aggiuntivi che danno un riferimento all’elemento successivo. Questa differenza nello schema di memorizzazione dei dati decide quale struttura di dati sarebbe più adatta per una data situazione.

Schema di memorizzazione dati di un array

Schema di memorizzazione dati di una lista collegata

Le principali differenze sono elencate di seguito:

• Dimensione: Poiché i dati possono essere memorizzati solo in blocchi contigui di memoria in un array, la loro dimensione non può essere modificata in fase di esecuzione a causa del rischio di sovrascrittura su altri dati. Tuttavia in una lista collegata, ogni nodo punta al successivo in modo tale che i dati possono esistere in indirizzi sparsi (non contigui); questo permette una dimensione dinamica che può cambiare in fase di esecuzione.
• Allocazione della memoria: Per gli array a tempo di compilazione e a tempo di esecuzione per le liste collegate.
• Efficienza della memoria: Per lo stesso numero di elementi, le liste collegate usano più memoria perché un riferimento al nodo successivo è anche memorizzato insieme ai dati. Tuttavia, la flessibilità delle dimensioni nelle liste collegate può far sì che usino complessivamente meno memoria; questo è utile quando c’è incertezza sulla dimensione o ci sono grandi variazioni nella dimensione degli elementi dei dati; la memoria equivalente al limite superiore della dimensione deve essere allocata (anche se non viene utilizzata tutta) mentre si usano gli array, mentre le liste collegate possono aumentare le loro dimensioni passo dopo passo in modo proporzionale alla quantità di dati.
• Tempo di esecuzione: Qualsiasi elemento in un array può essere raggiunto direttamente con il suo indice; tuttavia, nel caso di una lista collegata, tutti gli elementi precedenti devono essere attraversati per raggiungere qualsiasi elemento. Inoltre, una migliore localizzazione della cache negli array (dovuta all’allocazione di memoria contigua) può migliorare significativamente le prestazioni. Di conseguenza, alcune operazioni (come la modifica di un certo elemento) sono più veloci negli array, mentre altre (come l’inserimento/eliminazione di un elemento nei dati) sono più veloci nelle liste collegate.

Seguono i punti a favore delle liste collegate.
(1) La dimensione degli array è fissa: quindi dobbiamo conoscere in anticipo il limite superiore del numero di elementi. Inoltre, generalmente, la memoria allocata è uguale al limite superiore indipendentemente dall’uso, e negli usi pratici, il limite superiore è raramente raggiunto.

(2) Inserire un nuovo elemento in una matrice di elementi è costoso perché bisogna creare uno spazio per i nuovi elementi e per creare lo spazio gli elementi esistenti devono essere spostati.

Per esempio, supponiamo di mantenere una lista ordinata di ID in un array id.

id = .

E se vogliamo inserire un nuovo ID 1005, allora per mantenere l’ordine ordinato, dobbiamo spostare tutti gli elementi dopo 1000 (escluso 1000).

Anche la cancellazione è costosa con gli array fino a quando non si usano alcune tecniche speciali. Per esempio, per cancellare 1010 in id, tutto ciò che viene dopo 1010 deve essere spostato.

Quindi la lista collegata fornisce i seguenti due vantaggi rispetto agli array
1) Dimensione dinamica
2) Facilità di inserimento/cancellazione

Le liste collegate hanno i seguenti svantaggi:
1) L’accesso casuale non è permesso. Dobbiamo accedere agli elementi in modo sequenziale a partire dal primo nodo. Quindi non possiamo fare una ricerca binaria con le liste collegate.
2) È richiesto uno spazio di memoria extra per un puntatore con ogni elemento della lista.
3) Gli array hanno una migliore localizzazione nella cache che può fare una bella differenza nelle prestazioni.