Quelle est la complexité temporelle de l'ajout d'un élément au début d'un ArrayList?

Question

Disons que j'ai un ArrayList avec n éléments dans cet array, et j'ajoute un élément au début :

myArrayList.add(0,'some value');

Quelle sera la complexité temporelle de cette opération ?

Le Java Doc ne le spécifie pas.

Aussi

Je viens de commencer à apprendre Java, et j'ai vu la phrase

Un ArrayList en Java est une Liste qui est soutenue par un array.

Que signifie 'soutenu' ici ? Merci !

Answer 1

Ajouter un élément au début du tableau est en O(n) - cela nécessiterait de déplacer tous les éléments existants d'une position.

Tous les éléments dans une liste de tableaux sont stockés dans un tableau contigu. Si vous ajoutez plus d'éléments que la taille actuelle du tableau, il sera automatiquement agrandi pour accueillir le nouvel élément.

L'ajout à la fin est de O(1) amorti sur plusieurs insertions.

Answer 2

ArrayList.add(0, élément) prend du temps linéaire, mais la constante est très faible, car elle peut utiliser le très rapide System.arraycopy.

Answer 3

La documentation de l'ArrayList est en effet obscure sur ce point - je viens de la regarder dans SE11, et elle n'a pas changé depuis la première version du framework Collections (en Java 1.2).

Je pense que l'intention des auteurs de la documentation de l'ArrayList était de spécifier que, sur n'importe quelle implémentation de Java, l'opération d'ajout (c'est-à-dire la méthode add(E e)) doit s'exécuter en temps constant amorti, et que l'opération d'insertion dans la liste (c'est-à-dire la méthode add(int index, E e)) doit s'exécuter en temps O(n), où n est la taille de la liste.

Answer 4

• La construction de la liste à partir de zéro et l'ajout de nombreux éléments au début s'exécutent en temps quadratique : O(n2).
• Ajouter tous les éléments à la fin de la liste, puis appeler Collections.reverse(list) s'exécute en temps linéaire : O(n).