Question sur la FAQ collections

Bonjour à tous,

J'ai du mal à comprendre ceci :

Citation:

---

java.util.ArrayList :
Un java.util.ArrayList utilise un tableau en interne pour ranger les données. Un ArrayList fournit un accès aux éléments par leur indice très performant et est optimisé pour des opérations d'ajout/suppression d'éléments en fin de liste.
Complexité : Les opérations size, isEmpty, get, set, iterator sont exécutées en temps constant.
Les opérations d'ajout/suppression sont exécutées en temps constant amorti (les ajouts/suppressions en fin de liste sont plus rapides).

---

Ajout en temps constant amorti, ça me va, mais la suppression en temps constant amorti je vois pas, ou alors j'ai mal compris le "amorti"

Pour moi c'est en temps linéaire en fonction du nombre d’élément après l’élément à supprimer. Puisque ArrayList conserve l'ordre, on ne peut pas juste faire un swap avec le dernier élément, on est obligé de décaler les X élément apres de 1.

Du coup si vous pouvez m'éclairer je suis preneur :)

GrosLapin

Effectivement je la trouve pas d'une grande clarté, cette entrée -_-°.

L'ajout n'est en temps constant amorti que si c'est à la fin de la liste. Pour ajouter à la fin de la liste il faut qu'il y ait de la place dans le tableau, et s'il n'y en a pas il faut créer un tableau plus grand et copier le contenu de l'ancien tableau vers le nouveau, ce qui est en temps linéaire. Mais ArrayList s'arrange pour réserver un peu de place libre à la fin, chaque fois qu'il crée un nouveau tableau. Le résultat de tout ça, c'est que ajouter n éléments à la fin, a une complexité O(n), le temps constant amorti.

La suppression n'est en temps constant qu'à la fin de la liste. Ce n'est pas un amorti, c'est un temps constant pur et simple.

Ajout et suppression ailleurs, est en temps linéaire, comme tu le dis.

C'est bien ce que je pensais, merci pour la confirmation :)

GrosLapin