Quelle est la complexité d'ajouter un élément à ArrayList?

La complexité d'ajout d'un élément à ArrayList dans le cas moyen est de O(1).

Cela est réalisé grâce à l'utilisation d'un tableau dynamique, et l'ajout se fait à la fin de la liste.

// Ajout à la fin de la liste
List<String> list = new ArrayList<>();
list.add("élément"); // O(1) en moyenne

Cependant, si le tableau interne de ArrayList est plein, une opération d'agrandissement (resize) est nécessaire. Cela implique de créer un nouveau tableau plus grand et de copier tous les éléments existants dans le nouveau tableau. La complexité de cette opération est de O(n), où n est la taille actuelle de la liste.

// Exemple où un resize peut se produire
List<Integer> numbers = new ArrayList<>(3); // Capacité initiale de 3
numbers.add(1);
numbers.add(2);
numbers.add(3);
numbers.add(4); // Peut entraîner un resize - O(n)

Si l'élément est ajouté non à la fin de la liste (méthode add(int index, E element)), mais au milieu ou au début, tous les éléments suivants doivent être décalés d'une position vers la droite. La complexité de cette opération est de O(n), où n est le nombre d'éléments à décaler.

// Ajout au début de la liste
List<String> list = new ArrayList<>();
list.add("one");
list.add("two");
list.add(0, "zero"); // Ajout au début - O(n)

Ainsi, la complexité d'ajouter un élément à ArrayList dépend de l'endroit où il est ajouté et de la nécessité de resize:

Opération d'ajout	Cas moyen	Cas pire (lors du resize ou si non ajouté à la fin)
add(E element) (à la fin)	O(1)	O(n)
add(int index, E element)	O(n)	O(n)