Créer un tableau dynamique en Java

En Java, la longueur d’un tableau est fixe après sa création. Pour ajouter des éléments au-delà de cette longueur, on peut encapsuler un tableau ordinaire dans une classe de tableau dynamique qui suit le nombre de valeurs stockées et remplace le tableau sous-jacent lorsqu’il n’a plus de place. L’exemple ci-dessous stocke des valeurs primitives int, ajoute les éléments à la fin, supprime le dernier élément et peut réduire son espace de stockage pour qu’il corresponde à sa taille.

Créer un tableau dynamique avec une logique personnalisée en Java

La classe gère trois éléments d’état : le tableau sous-jacent int[], size et capacity. size correspond au nombre de valeurs actuellement stockées ; capacity correspond à la longueur du tableau sous-jacent. En séparant ces deux notions, le tableau peut réserver des emplacements sans les compter parmi les valeurs stockées.

Exécutez cet exemple :

Le code et les libellés ou sorties affichés dans cette section restent en anglais.

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());
    }
}

Sortie :

[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

Après cinq ajouts, les valeurs sont [10, 20, 30, 40, 50], avec une taille de 5 et une capacité de 8. Après removeLast(), les valeurs sont [10, 20, 30, 40], avec une taille de 4 et une capacité de 8. Après shrinkToSize(), la taille et la capacité sont toutes deux égales à 4.

Comprendre la taille, la capacité et le redimensionnement

Le constructeur commence avec une capacité de 2 et une taille de 0. À chaque appel de add, la classe vérifie si la taille a atteint la capacité. Lorsque le tableau sous-jacent est plein, Arrays.copyOf alloue un nouveau tableau deux fois plus long et y copie les valeurs existantes. La valeur suivante est alors écrite à l’index size, puis la taille augmente de un.

Pour les cinq ajouts présentés, la capacité passe de 2 à 4, puis à 8. Ces étapes de croissance copient les valeurs stockées ; les emplacements libres du nouveau tableau pourront accueillir les ajouts suivants. La capacité décrit l’espace alloué, et non le nombre de valeurs. La méthode toString() ne copie que la partie située avant la taille : les emplacements libres ne sont donc pas affichés comme des éléments.

La durée de la copie est proportionnelle au nombre de valeurs copiées, et les deux tableaux doivent temporairement coexister. Le doublement évite une copie à chaque ajout, même si un ajout qui déclenche une croissance entraîne bien une copie. Cette petite classe sert à illustrer le mécanisme ; pour les collections à usage général, ArrayList<Integer> est généralement un meilleur choix en Java.

Ajouter et supprimer des éléments

add permet uniquement d’ajouter un élément à la fin ; cette méthode ne l’insère pas à un index arbitraire. removeLast réduit la taille de un et remet l’emplacement libéré à la valeur int par défaut de Java, 0. Comme int est un type primitif et non une référence, cette remise à zéro n’est pas nécessaire au ramasse-miettes : elle sert simplement à rendre prévisible la partie inutilisée du tableau sous-jacent. Si la taille est de 0, appeler removeLast ne modifie pas l’objet.

La suppression ne réduit pas automatiquement la capacité. Appelez shrinkToSize() lorsque récupérer les emplacements libres du tableau compte davantage que conserver de la place pour de futurs ajouts. Le redimensionnement copie lui aussi les valeurs dans un tableau de remplacement. Si la taille est de 0, la capacité devient 0 ; le prochain appel à add la fait passer à 1 avant d’enregistrer la nouvelle valeur. L’implémentation ne stocke que des valeurs primitives int et ne fournit ni accès par index, ni insertion, ni suppression au milieu du tableau.