Java ArrayList

ArrayList<E> è l'implementazione di List più utilizzata. Internamente è un semplice array Java (Object[]) con un contatore di lunghezza e della logica di crescita sopra. Questo le conferisce le prestazioni che la maggior parte del codice desidera: accesso casuale O(1), append ammortizzato O(1) in fondo, e solo la pausa occasionale quando l'array sottostante deve crescere. Quando qualcuno dice "usa una lista" senza specificarne il tipo, quasi sempre intende ArrayList. Questo capitolo spiega il perché, quali sono i compromessi e i pochi metodi unici della classe.

Cosa contiene

Un ArrayList contiene tre pezzi di stato:

• Object[] elementData — l'array sottostante. Più grande di size di qualche margine.
• int size — quanti di quegli slot sono in uso.
• int modCount — un contatore che fa fallire gli iteratori se si muta durante l'iterazione.

Il Javadoc è preciso riguardo alla complessità: size, isEmpty, get, set, iterator, listIterator e add (in fondo) girano tutti in tempo costante. Inserire / rimuovere altrove è lineare perché la coda dell'array deve scorrere. Torneremo su questo.

Crearne uno

List<String> a = new ArrayList<>();             // default capacity (10)
List<String> b = new ArrayList<>(1_000_000);    // pre-size — avoids re-grows
List<String> c = new ArrayList<>(otherList);    // copy of any Collection
List<String> d = new ArrayList<>(List.of("a", "b", "c"));   // from a small literal

Se sai più o meno quanti elementi aggiungerai, passa la capacità al costruttore. La capacità predefinita è 10, e ogni volta che l'array si riempie cresce di circa il 50% — il che significa molte allocazioni e copie se si aggiungono milioni di elementi partendo dal default. Correzione in una riga:

List<Row> rows = new ArrayList<>(expectedSize);

Per "da questo insieme fisso", preferisci la factory List.of(...) (trattata più avanti in questo capitolo) — è più piccola e immutabile.

Aggiungere e rimuovere — il costo dipende dalla posizione

Ogni List.add(E) e add(int, E) e remove(int) e remove(Object) è O(n) nel caso peggiore se tocca il mezzo dell'array. Il motivo è meccanico: un array è memoria contigua, quindi inserire in testa significa che ogni elemento esistente deve spostarsi di uno slot a destra. Il costo ammortizzato dell'append in fondo è O(1) (nessuno spostamento), ma ogni altra posizione è lineare rispetto al numero di elementi dopo il punto di inserimento.

In pratica ciò significa:

• Costruire una lista con list.add(x) ripetuto → veloce, indipendentemente dalla dimensione. L'append in fondo è ciò per cui ArrayList è pensato.
• Chiamare list.add(0, x) in un ciclo → quadratico. Non farlo.
• Chiamare list.remove(0) ripetutamente per svuotarla → quadratico. Usa una Deque o itera al contrario.

Se ti trovi costantemente a inserire o rimuovere in testa, ArrayDeque è lo strumento giusto.

Capacità vs. dimensione

Questi sono due numeri diversi:

• size() è il conteggio degli elementi a livello pubblico, contrattuale.
• La capacità — la lunghezza dell'array sottostante — è interna ed è maggiore di size.

Quando il margine si esaurisce, ArrayList alloca un nuovo array di circa 1,5× la lunghezza precedente e copia. Questa è la "crescita" di cui il Javadoc avverte. Due leve di controllo:

• ensureCapacity(int) — porta l'array sottostante ad almeno quella lunghezza prima di una serie nota di chiamate add.
• trimToSize() — riduce l'array sottostante esattamente a size. Utile quando sai che la lista non crescerà più (es. prima di metterla in cache per molto tempo).

Nessuna delle due è qualcosa che userai spesso, ma vale la pena sapere che esistono quando stai ottimizzando un percorso critico.

ArrayList non è thread-safe

Due thread che modificano lo stesso ArrayList lo corromperanno prima o poi. Non c'è sincronizzazione, nessuna operazione atomica, nulla. Se hai bisogno di accesso concorrente, le opzioni sono:

• Collections.synchronizedList(new ArrayList<>()) — avvolge ogni mutatore in un lock. Gli iteratori non sono ancora sicuri — devi sincronizzare esternamente durante l'iterazione. Va bene per casi a bassa contesa.
• CopyOnWriteArrayList — ogni mutazione alloca una nuova copia dell'array sottostante. L'iterazione è lock-free e vede uno snapshot congelato. Brillante per "molti lettori, scrittore occasionale" (ascoltatori di eventi, cache di configurazione). Pessimo per carichi di lavoro pesanti in scrittura.
• Vector — anche sincronizzato, ma una progettazione del 1995 con gli stessi difetti di synchronizedList. Non sceglierlo per nuovo codice.

Il threading è un argomento profondo a sé stante; per ora la regola è: un ArrayList condiviso tra thread ha bisogno di un wrapper o di una classe diversa.

Iterazione e ConcurrentModificationException

Aggiungere o rimuovere da un ArrayList mentre lo si itera con il ciclo for-each lancia quasi sempre ConcurrentModificationException:

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

Il controllo fail-fast confronta lo snapshot di modCount dell'iteratore con il modCount corrente della lista. I due modi per mutare in sicurezza:

xs.removeIf(x -> x % 2 == 0);              // 1. predicate form — cleanest

Iterator<Integer> it = xs.iterator();
while (it.hasNext())                        // 2. explicit Iterator.remove()
  if (it.next() % 2 == 0) it.remove();

removeIf è il default moderno. Ricorri all'iteratore esplicito solo quando la condizione dipende da uno stato che non vuoi calcolare due volte.

Metodi utili non presenti su List

ArrayList aggiunge alcuni metodi che l'interfaccia List non ha:

• void trimToSize() — riduce al minimo.
• void ensureCapacity(int) — pre-crescita.
• Object clone() — copia superficiale. Equivalente a new ArrayList<>(this) e quasi mai usato.

È tutto. Quasi tutto ciò che chiamerai su un ArrayList proviene dall'interfaccia List.

Un esempio pratico: ArrayList in azione

Il programma seguente costruisce un ArrayList, esercita le sue operazioni basate su indice, lo svuota e termina con la differenza di timing tra pre-crescita della capacità e crescita predefinita, così puoi vedere il costo di dimenticarsi di pre-dimensionare.

L'ordine delle operazioni da leggere nell'output:

• fruits.add(1, "avocado") ha spostato ogni elemento successivo di uno slot a destra. Per quattro elementi è invisibile; per un milione dominerebbe il tempo di esecuzione.
• removeIf e subList sono i due meccanismi che rendono pulito la maggior parte del codice ArrayList reale — rimozione massiva basata su predicato e operazioni su finestre live.
• Il blocco di timing è illustrativo, non di livello benchmark — in una singola esecuzione con riscaldamento JIT i numeri possono persino uscire al contrario. Il punto che fa è strutturale: l'append con capacità predefinita fa ricrescere l'array sottostante circa 30 volte entro il milionesimo elemento, e il pre-dimensionamento elimina ognuna di quelle copie. Per un percorso critico in stato stazionario la versione pre-dimensionata vince; misura con un harness appropriato se è importante.

Cosa c'è dopo

ArrayList è quasi sempre la risposta giusta. Il caso interessante è quando non lo è — inserimento e rimozione frequenti in testa o al centro di una lista lunga. Questa è la nicchia di LinkedList: stessa interfaccia List, archiviazione completamente diversa. Stesso problema, due risposte — e misureremo quando ciascuna vince.

Esercitati