Entrambi memorizzano sequenze, ma hanno profili di costo opposti. Un array è memoria contigua con accesso O(1) per indice; una linked list è un insieme di nodi sparsi collegati da puntatori, con inserimento/rimozione O(1) alle estremità ma senza accesso per indice.
| Operazione | Array (dinamico) | Linked list |
|---|
| Accesso per indice | O(1) | O(n) |
| Ricerca | O(n) | O(n) |
| Inserimento/rimozione all'inizio | O(n) | O(1) |
| Inserimento/rimozione alla fine | O(1) ammortizzato | O(1) con tail ptr |
| Inserimento/rimozione nel mezzo | O(n) | O(n) ricerca + O(1) splice |
| Overhead di memoria | basso | alto (puntatore per nodo) |
| Località della cache | eccellente | scarsa |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
Nella pratica gli array vincono la maggior parte delle volte perché la località della cache supera le differenze Big-O per dimensioni tipiche.
Conoscere entrambi ti permette di giustificare la tua scelta nei colloqui invece di scegliere alla cieca — e di spiegare perché "inserimento O(1)" raramente batte un array contiguo.