0Pricing
Java Academy · Lezione

LinkedList e ArrayList a confronto

Confronti le prestazioni di inserimento, eliminazione e accesso casuale per scegliere il tipo di lista più adatto.

LinkedList e ArrayList a confronto è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

La domanda fondamentale

Sia ArrayList sia LinkedList implementano List, quindi condividono la stessa API. La differenza risiede nelle strutture dati interne e nelle operazioni che ciascuna esegue in modo efficiente.

Struttura interna di ArrayList

ArrayList memorizza gli elementi in un array contiguo. Quando l'array si riempie, viene sostituito con un nuovo array più grande di 1,5 volte e tutti gli elementi vengono copiati.

import java.util.ArrayList;

ArrayList<String> list = new ArrayList<>(4); // initial capacity 4
list.add("A"); list.add("B"); list.add("C"); list.add("D");
list.add("E"); // triggers resize: new array of capacity 6

System.out.println(list.get(3)); // O(1) — direct index access

Struttura interna di LinkedList: riepilogo

Ogni elemento risiede in un proprio oggetto Node con puntatori prev/next. Non c'è memoria contigua: i nodi possono trovarsi in qualsiasi posizione nell'heap.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();
list.add("A"); list.add("B"); list.add("C");

// get(index) must traverse from head or tail
System.out.println(list.get(1)); // O(n) — traverses 1 step from head

Accesso casuale: vince ArrayList

ArrayList.get(i) ha complessità O(1): accesso diretto tramite indice dell'array. LinkedList.get(i) ha complessità O(n): attraversa fino a n/2 nodi.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();
for (int i = 0; i < 100_000; i++) { al.add(i); ll.add(i); }

// Fast:
System.out.println(al.get(99_999)); // O(1)

// Slow — avoid this pattern with LinkedList:
System.out.println(ll.get(99_999)); // O(n)

Inserimenti in testa: vince LinkedList

L'aggiunta all'indice 0 in ArrayList richiede lo spostamento di tutti gli elementi, con complessità O(n). LinkedList aggiorna semplicemente due puntatori, con complessità O(1).

// ArrayList: O(n) — shifts all elements right
ArrayList<String> al = new ArrayList<>(List.of("B","C","D"));
al.add(0, "A"); // shifts B, C, D

// LinkedList: O(1)
LinkedList<String> ll = new LinkedList<>(List.of("B","C","D"));
ll.addFirst("A"); // updates head pointer only

Inserimenti in coda: sostanzialmente equivalenti

Sia ArrayList sia LinkedList offrono inserimenti in coda con complessità ammortizzata O(1). ArrayList attiva occasionalmente una copia durante il ridimensionamento, ma la complessità ammortizzata resta O(1). LinkedList alloca un nuovo nodo, senza bisogno di ridimensionare.

ArrayList<Integer> al = new ArrayList<>();
LinkedList<Integer> ll = new LinkedList<>();

for (int i = 0; i < 1_000_000; i++) {
    al.add(i); // amortized O(1)
    ll.add(i); // O(1)
}

Utilizzo della memoria

ArrayList: circa 8 byte per elemento, ovvero un riferimento nell'array. LinkedList: circa 48 byte per elemento, ovvero un oggetto Node con dati, prev, next e intestazione dell'oggetto. Per dataset di grandi dimensioni, ArrayList utilizza molta meno memoria.

Prestazioni dell'iterazione

L'iterazione sequenziale, con for-each o iterator, ha complessità O(n) per entrambe. Tuttavia, ArrayList beneficia del prefetching della cache della CPU: gli elementi sono contigui in memoria. I nodi di LinkedList sono distribuiti nell'heap e causano cache miss.

// Both O(n), but ArrayList is faster in practice due to cache locality
for (String s : arrayList) { process(s); }
for (String s : linkedList) { process(s); } // more cache misses

Inserimento ed eliminazione nel mezzo

Entrambe richiedono O(n) per trovare la posizione. Una volta trovata, ArrayList sposta gli elementi con complessità O(n), mentre LinkedList scollega semplicemente il nodo con complessità O(1). Quindi, per modifiche frequenti nel mezzo quando si dispone già di un iteratore, vince LinkedList; altrimenti sono simili.

LinkedList<Integer> ll = new LinkedList<>(List.of(1,2,3,4,5));
ListIterator<Integer> it = ll.listIterator();
while (it.hasNext()) {
    int val = it.next();
    if (val == 3) it.remove(); // O(1) unlink via iterator
}
System.out.println(ll); // [1, 2, 4, 5]

Guida alla scelta

Scelga in base all'operazione dominante:

  • ArrayList: accesso casuale, iterazione e inserimenti in coda; copre il 90% dei casi d'uso
  • LinkedList: frequenti inserimenti e rimozioni in testa o in coda, implementazione di code, deque o stack
  • ArrayDeque: quando serve esclusivamente una coda o uno stack, è migliore di LinkedList

Riepilogo del benchmark

Modello mentale delle prestazioni:

  • get(i): ArrayList O(1) rispetto a LinkedList O(n)
  • add(0,x): ArrayList O(n) rispetto a LinkedList O(1)
  • add(x): O(1) ammortizzato per entrambe
  • rimozione tramite iterator: O(1) per entrambe una volta raggiunta la posizione
  • Memoria per elemento: ArrayList circa 8 B rispetto a LinkedList circa 48 B

Verifica rapida

Sta creando una coda di attività in cui le attività vengono aggiunte in coda e rimosse dalla testa milioni di volte al secondo. Quale struttura dati è più appropriata?

Riepilogo: LinkedList vs ArrayList

Punti chiave:

  • ArrayList è eccellente per l'accesso casuale (O(1)) e per l'iterazione efficiente rispetto alla cache
  • LinkedList è eccellente per le operazioni O(1) in testa e in coda
  • Memoria: circa 8 B per elemento con ArrayList; circa 48 B per elemento con LinkedList
  • Per code e stack, preferisca ArrayDeque a LinkedList
  • ArrayList è la scelta predefinita più adatta nella maggior parte degli scenari

Domande Frequenti

La lezione «LinkedList e ArrayList a confronto» è gratuita?

Sì — il testo completo di «LinkedList e ArrayList a confronto» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «LinkedList e ArrayList a confronto»?

Confronti le prestazioni di inserimento, eliminazione e accesso casuale per scegliere il tipo di lista più adatto. Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.

Quanto tempo richiede la lezione «LinkedList e ArrayList a confronto»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

  1. Internals di LinkedList
  2. Operazioni su Deque: stack e queue
  3. LinkedList e ArrayList a confronto
  4. PriorityQueue per l'elaborazione ordinata
← Torna a Java Academy