Crea un array dinamico in Java

In Java, gli array hanno una lunghezza fissa dopo la creazione. Per aggiungere elementi oltre tale limite, si può racchiudere un normale array in una classe di array dinamico che tiene traccia dei valori memorizzati e sostituisce l’array sottostante quando lo spazio termina. L’esempio seguente memorizza valori primitivi int, aggiunge elementi in fondo, rimuove l’ultimo valore e può ridurre lo spazio allocato per adattarlo alla dimensione corrente.

Creare un array dinamico con una logica personalizzata in Java

La classe gestisce tre elementi di stato: l’array int[] sottostante, size e capacity. La dimensione indica quanti valori sono attualmente memorizzati; la capacità è la lunghezza dell’array sottostante. Mantenere separati questi valori permette di riservare posizioni senza considerarle valori memorizzati.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

import java.util.Arrays;

public class DynamicArray {
    private int[] values;
    private int size;

    public DynamicArray() {
        values = new int[2];
    }

    public void add(int value) {
        if (size == values.length) {
            int newCapacity = values.length == 0 ? 1 : values.length * 2;
            values = Arrays.copyOf(values, newCapacity);
        }
        values[size] = value;
        size++;
    }

    public void removeLast() {
        if (size == 0) {
            return;
        }
        size--;
        values[size] = 0;
    }

    public void shrinkToSize() {
        values = Arrays.copyOf(values, size);
    }

    public int size() {
        return size;
    }

    public int capacity() {
        return values.length;
    }

    @Override
    public String toString() {
        return Arrays.toString(Arrays.copyOf(values, size));
    }

    public static void main(String[] args) {
        DynamicArray numbers = new DynamicArray();
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());

        numbers.removeLast();
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());

        numbers.shrinkToSize();
        System.out.println(numbers + " | size=" + numbers.size()
                + " | capacity=" + numbers.capacity());
    }
}

Output:

[10, 20, 30, 40, 50] | size=5 | capacity=8
[10, 20, 30, 40] | size=4 | capacity=8
[10, 20, 30, 40] | size=4 | capacity=4

Dopo cinque aggiunte, i valori sono [10, 20, 30, 40, 50], con dimensione 5 e capacità 8. Dopo removeLast(), i valori sono [10, 20, 30, 40], con dimensione 4 e capacità 8. Dopo shrinkToSize(), dimensione e capacità sono entrambe 4.

Capire dimensione, capacità e ridimensionamento

Il costruttore parte da una capacità pari a 2 e da una dimensione pari a 0. Ogni chiamata a add verifica se la dimensione ha raggiunto la capacità. Quando l’array sottostante è pieno, Arrays.copyOf alloca un nuovo array lungo il doppio e vi copia i valori esistenti. Il valore successivo viene quindi scritto all’indice size e la dimensione aumenta di uno.

Per le cinque aggiunte mostrate, la capacità passa da 2 a 4 e poi a 8. Durante ogni espansione vengono copiati i valori memorizzati; le posizioni libere nel nuovo array restano disponibili per aggiunte successive. La capacità descrive lo spazio allocato, non il numero di valori. Il metodo toString() copia solo la parte che precede la dimensione, quindi le posizioni libere non compaiono tra gli elementi.

La copia richiede un tempo proporzionale al numero di valori copiati e, per un breve periodo, entrambi gli array devono esistere. Raddoppiare la capacità evita una copia a ogni aggiunta, anche se la singola aggiunta che provoca l’espansione comporta comunque una copia. Questa piccola classe serve a mostrare il meccanismo; per le raccolte di uso generale, di solito è preferibile ArrayList<Integer> di Java.

Aggiungere e rimuovere elementi

add consente solo di aggiungere elementi in fondo; non inserisce valori a un indice arbitrario. removeLast riduce la dimensione di uno e azzera lo slot liberato, assegnandogli il valore predefinito di int in Java, cioè 0. Poiché int è un tipo primitivo, non un riferimento, azzerare lo slot non serve alla garbage collection: serve soltanto a mantenere prevedibile la parte inutilizzata dell’array sottostante. Se la dimensione è 0, chiamare removeLast lascia l’oggetto invariato.

La rimozione non riduce automaticamente la capacità. Chiama shrinkToSize() quando recuperare le posizioni libere dell’array è più importante che mantenere spazio per le aggiunte successive. Anche il ridimensionamento ridotto copia i valori in un array sostitutivo. Se la dimensione è 0, la capacità diventa 0; alla chiamata successiva di add, la capacità passa a 1 prima che venga memorizzato il nuovo valore. L’implementazione memorizza solo valori primitivi int e non offre accesso tramite indice, inserimento o rimozione di elementi intermedi.