Quelle est la complexité temporelle de l'opération d'insertion d'un élément au début d'une ArrayList dynamique?

L'insertion d'un élément au début d'un tableau dynamique (par exemple, ArrayList en Java) a une complexité temporelle de O(n), où n est le nombre d'éléments dans le tableau.

Cela est dû au fait qu'à l'insertion au début, tous les éléments existants doivent être décalés d'une position vers la droite pour faire de la place pour le nouvel élément. Le processus de copie des éléments prend un temps linéaire.

Exemple :

ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);

// Insertion au début
list.add(0, 0); // décale tous les éléments vers la droite

Ainsi, l'insertion à la fin est généralement plus rapide (amortie O(1)), tandis que celle au début est O(n).