Java LinkedList

LinkedList<E> è una lista doppiamente collegata: ogni elemento vive nel proprio nodo heap con un puntatore al nodo successivo e uno al precedente. Questo le conferisce il profilo di prestazioni opposto a ArrayList: inserimento e rimozione alle estremità è O(1), ma get(i) deve scorrere da un'estremità all'indice — O(n). La classe è anche l'unica List built-in di Java che implementa anche Deque<E>, quindi funge anche da coda. Questo capitolo spiega quando questa combinazione è lo strumento giusto, e i casi (un po' più numerosi) in cui non lo è.

La struttura dati

Ogni elemento è un nodo:

node:  prev ←—— element ——→ next

La lista mantiene due riferimenti ai campi — first e last — e un contatore size. Per aggiungere a entrambe le estremità, si alloca un nodo, lo si inserisce aggiustando due puntatori, e si incrementa size. Nessun array, nessun ridimensionamento, nessuna memoria sprecata. Questo è il suo punto di forza.

Il costo si manifesta altrove:

• Ogni elemento paga per un oggetto nodo — tre riferimenti e un'intestazione oggetto. L'overhead di memoria per elemento è molto più alto rispetto all'array piatto di ArrayList.
• get(i), set(i, x), add(i, x), remove(i) scorrono tutti dall'estremità più vicina. Quindi list.get(size/2) è O(n/2). Per liste lunghe, questo si accumula negativamente.
• La località della cache è scarsa — i nodi sono dispersi nell'heap, quindi l'attraversamento manca la cache della CPU e rallenta anche quando l'algoritmo sembra lineare.

Quando LinkedList è la scelta giusta

La risposta onesta nel 2026: raramente come List, a volte come Deque, quasi mai per "velocizzare gli inserimenti." Il luogo comune "usa LinkedList perché devi inserire elementi" non ha retto bene alla prova del tempo — per la maggior parte dei carichi di lavoro, la cache-friendliness di ArrayList più il suo append O(1) ammortizzato batte l'inseguimento di puntatori aggiuntivo di una lista collegata, anche quando l'algoritmo chiama add(0, x) a volte. I casi in cui LinkedList vince davvero:

• Hai bisogno di un Deque (aggiungi/rimuovi da entrambe le estremità) e non hai già un ArrayDeque a portata di mano. ArrayDeque è più veloce; LinkedList è più familiare.
• Mantieni riferimenti persistenti a nodi specifici (tramite ListIterator) e vuoi un inserimento/rimozione O(1) in quelle esatte posizioni. Questo è il classico caso d'uso delle liste collegate — e quasi mai si presenta nel Java quotidiano.
• Vuoi un'implementazione Queue che espone anche i metodi List per l'ispezione. Esempio reale: una coda di lavori che occasionalmente viene scaricata in un log.

Per "lista a cui aggiungere elementi e leggere per indice," usa ArrayList. Per "coda o deque," usa ArrayDeque. LinkedList si trova nel mezzo e raramente è la soluzione migliore per entrambi i compiti.

Crearla e usarla come List

La metà List dell'API è identica ad ArrayList:

List<String> tasks = new LinkedList<>();
tasks.add("compile");
tasks.add("test");
tasks.add(0, "lint");          // O(1) — at the head
String first = tasks.get(0);   // O(1) — head
String last  = tasks.get(tasks.size() - 1);   // O(1) — tail
String mid   = tasks.get(tasks.size() / 2);   // O(n/2) — has to walk

Il costruttore non ha un parametro di capacità — non c'è nulla da pre-dimensionare, perché i nodi vengono allocati uno alla volta.

Usarla come Queue e Deque

Poiché LinkedList implementa sia Queue<E> che Deque<E>, si ottengono i metodi della coda in aggiunta a quelli della List:

Deque<String> stack = new LinkedList<>();
stack.push("a");          // adds to head
stack.push("b");
String top = stack.pop(); // removes from head → "b"

Queue<String> jobs = new LinkedList<>();
jobs.offer("j1");         // adds to tail
jobs.offer("j2");
String next = jobs.poll();// removes from head → "j1"

Se la necessità è puramente "coda FIFO" o "stack LIFO," dichiara la variabile come Queue<E> o Deque<E> — e preferisci new ArrayDeque<>() come implementazione. L'interfaccia è la stessa; l'implementazione basata su array è misurabilmente più veloce.

Iterazione e ConcurrentModificationException

Stesso modello fail-fast di ArrayList. Modificare durante un ciclo for-each lancia un'eccezione:

LinkedList<Integer> xs = new LinkedList<>(List.of(1, 2, 3, 4));
for (int x : xs) if (x % 2 == 0) xs.remove(Integer.valueOf(x));  // throws

removeIf e l'Iterator.remove() esplicito sono le due forme sicure — identiche al capitolo su ArrayList. La variante interessante per LinkedList è il ListIterator: poiché l'iteratore mantiene un riferimento diretto al nodo corrente, i suoi add e remove sono genuinamente O(1). Se hai davvero bisogno di un inserimento rapido in posizione durante l'iterazione, LinkedList.listIterator() è l'API che mantiene la promessa del libro di testo.

Thread safety

Stessa storia di ArrayList: nessuna. Usa Collections.synchronizedList(new LinkedList<>()) per un blocco generale, o — molto meglio — un ConcurrentLinkedDeque se il tuo caso d'uso è davvero una coda concorrente.

Il confronto con ArrayDeque in un paragrafo

Quando stai per usare LinkedList come coda o stack, guarda prima ArrayDeque. ArrayDeque è un array circolare — nessun nodo per elemento, nessun inseguimento di puntatori, nessuna regola di rifiuto null da ricordare. Su carichi di lavoro stack/coda grandi e reali, di solito supera LinkedList — a volte con ampio margine — perché evita un nodo heap e un'intestazione per elemento e mantiene i dati contigui in memoria. Non implementa List, che è il suo unico vero svantaggio. (Non sovra-interpretare un piccolo benchmark in nessuna direzione; vedi l'esempio pratico sotto.)

Un esempio pratico: stesso lavoro, due strutture dati

Il programma seguente costruisce la stessa coda con ArrayList, LinkedList e ArrayDeque — push a un'estremità, pop dall'altra 200 000 volte — e stampa il tempo reale per ciascuno. Leggi i numeri nel contesto: sono un micro-benchmark approssimativo a singola esecuzione su una JVM fredda, non un risultato rigoroso, quindi considera l'ordine relativo — non i millisecondi esatti — come la lezione. ArrayList è drammaticamente più lento degli altri due perché remove(0) è O(n), quindi il ciclo di svuotamento è quadratico. LinkedList e ArrayDeque sono entrambi veloci: ciascuno esegue lavoro O(1) in testa. Quale dei due sia più veloce dipende dalla macchina, dal JIT e dal boxing di Integer — è esattamente per questo che non dovresti mai affidarti a un benchmark così piccolo per scegliere tra loro.

Due conclusioni:

• I primi due tempi mostrano perché non bisogna mai indicizzare una LinkedList in un ciclo. La forma for-each scorre la lista una volta in O(n); la forma con indice la scorre una volta per ogni indice, dando O(n²). Per 10 000 elementi è già doloroso; per 100 000 sono secondi.
• I tre tempi della coda mostrano la vera divisione: è tra ArrayList (svuotamento quadratico) e le due strutture O(1)-in-testa, non tra LinkedList e ArrayDeque. Una volta escluso ArrayList per il lavoro con code, preferisci comunque ArrayDeque — non alloca nessun nodo per elemento e ha una località della cache molto migliore su code grandi e longeve, che un ciclo cold-start da 200 000 elementi non espone completamente. Il motivo genuino rimanente per usare LinkedList è "voglio un Deque e una List," e anche quello è raro.

Cosa c'è dopo

LinkedList e ArrayList sono le due implementazioni List di uso generale più interessanti. La terza — più vecchia, sincronizzata, per lo più storica — è Vector. Capire perché non è la scelta giusta nel nuovo codice fa parte della padronanza del framework.

Esercizio