Java ArrayList

ArrayList<E> est l'implémentation de List la plus couramment utilisée. En interne, il s'agit d'un simple tableau Java (Object[]) avec un compteur de longueur et une logique de croissance par-dessus. Cela lui confère le profil de performances que la plupart du code recherche : accès aléatoire en O(1), ajout amorti en O(1) en fin de tableau, et seulement une pause occasionnelle quand le tableau sous-jacent doit croître. Quand quelqu'un dit « utilise une liste » sans préciser laquelle, il veut presque toujours dire ArrayList. Ce chapitre explique pourquoi, quels sont les compromis, et les quelques méthodes propres à cette classe.

Ce qui se passe en interne

Un ArrayList conserve trois éléments d'état :

• Object[] elementData — le tableau sous-jacent. Plus grand que size d'une certaine marge.
• int size — le nombre de cases effectivement utilisées.
• int modCount — un compteur qui fait échouer les itérateurs si vous mutez pendant l'itération.

La Javadoc est précise sur la complexité : size, isEmpty, get, set, iterator, listIterator et add (en fin de liste) s'exécutent tous en temps constant. Insérer ou supprimer ailleurs est linéaire, car la queue du tableau doit se décaler. Nous y reviendrons.

Création

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

Si vous savez à peu près combien d'éléments vous allez ajouter, passez la capacité au constructeur. La capacité par défaut est 10, et chaque fois que le tableau est plein il croît d'environ 50 % — ce qui implique beaucoup d'allocations et de copies si vous ajoutez des millions d'éléments depuis la valeur par défaut. Correction en une ligne :

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

Pour « à partir de cet ensemble fixe », préférez la fabrique List.of(...) (abordée plus loin dans ce chapitre) — elle est plus compacte et immuable.

Ajout et suppression — le coût dépend de l'endroit

Chaque List.add(E), add(int, E), remove(int) et remove(Object) est O(n) dans le pire cas s'il touche le milieu du tableau. La raison est mécanique : un tableau est une zone mémoire contiguë, donc insérer en tête signifie que chaque élément existant doit se décaler d'une case vers la droite. Le coût amorti de l'ajout en fin de liste est O(1) (aucun décalage), mais toute autre position est linéaire en fonction du nombre d'éléments après le point d'insertion.

En pratique, cela signifie :

• Construire une liste par des list.add(x) répétés → rapide, quelle que soit la taille. L'ajout en fin de liste est la vocation de ArrayList.
• Appeler list.add(0, x) dans une boucle → quadratique. À éviter.
• Appeler list.remove(0) répétitivement pour vider la liste → quadratique. Utilisez un Deque ou itérez en sens inverse.

Si vous vous retrouvez à insérer ou supprimer constamment en tête, ArrayDeque est le bon outil.

Capacité vs. taille

Ce sont deux nombres distincts :

• size() est le nombre d'éléments au niveau public, contractuel.
• La capacité — la longueur du tableau sous-jacent — est interne et plus grande que size.

Quand la marge est épuisée, ArrayList alloue un nouveau tableau d'environ 1,5 fois l'ancienne longueur et copie. C'est la « croissance » dont la Javadoc avertit. Deux leviers de contrôle :

• ensureCapacity(int) — agrandit le tableau sous-jacent à au moins cette longueur avant une rafale connue d'appels add.
• trimToSize() — réduit le tableau sous-jacent à exactement size. Utile une fois que vous savez que la liste ne grandira plus (par exemple, avant de la mettre en cache longtemps).

Ni l'un ni l'autre ne seront utilisés souvent, mais il est utile de savoir qu'ils existent quand vous optimisez un chemin critique.

ArrayList n'est pas thread-safe

Deux threads qui modifient le même ArrayList finiront par le corrompre. Il n'y a pas de synchronisation, pas d'opération atomique, rien. Si vous avez besoin d'un accès concurrent, vos options sont :

• Collections.synchronizedList(new ArrayList<>()) — enveloppe chaque mutateur dans un verrou. Les itérateurs ne sont toujours pas sûrs — vous devez synchroniser en externe pendant l'itération. Convient pour les cas à faible contention.
• CopyOnWriteArrayList — chaque mutation alloue une nouvelle copie du tableau sous-jacent. L'itération est sans verrou et voit un instantané figé. Idéal pour « beaucoup de lecteurs, écrivain occasionnel » (écouteurs d'événements, caches de configuration). Catastrophique pour les charges intensives en écriture.
• Vector — aussi synchronisé, mais une conception de 1995 avec les mêmes faiblesses que synchronizedList. Ne le choisissez pas pour du nouveau code.

La gestion des threads est un sujet à part entière ; pour l'instant, la règle est : un ArrayList partagé entre threads a besoin d'un wrapper ou d'une autre classe.

Itération et ConcurrentModificationException

Ajouter ou supprimer d'un ArrayList pendant qu'on l'itère via la boucle for-each lève presque toujours une 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
}

La vérification fail-fast compare l'instantané de modCount de l'itérateur avec le modCount actuel de la liste. Les deux façons de muter en toute sécurité :

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 est le choix moderne par défaut. Recourez à l'itérateur explicite uniquement quand la condition dépend d'un état que vous ne voulez pas calculer deux fois.

Méthodes utiles absentes de List

ArrayList ajoute quelques méthodes que l'interface List n'a pas :

• void trimToSize() — réduit au strict nécessaire.
• void ensureCapacity(int) — pré-agrandit.
• Object clone() — copie superficielle. Équivalent à new ArrayList<>(this) et presque jamais utilisé.

C'est tout. Presque tout ce que vous appellerez sur un ArrayList vient de l'interface List.

Un exemple concret : ArrayList en action

Le programme ci-dessous construit un ArrayList, exercice ses opérations basées sur les indices, le vide, et termine par la comparaison de temps entre pré-dimensionnement et dimensionnement par défaut pour un million d'ajouts, afin de vous montrer le coût d'oublier le pré-dimensionnement.

L'ordre des opérations à lire dans la sortie :

• fruits.add(1, "avocado") a décalé chaque élément suivant d'une case vers la droite. Pour quatre éléments, c'est invisible ; pour un million, cela dominerait le temps d'exécution.
• removeIf et subList sont les deux mécanismes qui rendent la plupart du code ArrayList réel propre — suppression en masse basée sur un prédicat et opérations sur une fenêtre vivante.
• Le bloc de mesure est illustratif, pas de qualité benchmark — sur une seule exécution avec échauffement JIT, les chiffres peuvent même s'inverser. Le point structurel qu'il illustre est le suivant : l'ajout avec capacité par défaut fait croître le tableau sous-jacent environ 30 fois au millionième élément, et le pré-dimensionnement élimine chacune de ces copies. Pour un chemin critique en régime permanent, la version pré-dimensionnée l'emporte ; mesurez avec un harness approprié si cela compte.

Et ensuite

ArrayList est presque toujours la bonne réponse. Le cas intéressant est celui où ce n'est pas le cas — insertions et suppressions intensives en tête ou au milieu d'une longue liste. C'est le créneau de LinkedList : même interface List, stockage complètement différent. Même problème, deux réponses — et nous mesurerons quand chacune l'emporte.

Pratique