java Temps de traitement de la liste

Question

Ceci est tiré de wikipedia : http://en.wikipedia.org/wiki/Arraylist sous Performance .

ArrayList : temps constant pour remove(), add() à la fin du tableau, temps linéaire pour add(), remove() au début.

LinkedList : les deux opérations énoncées : temps constant, indexation : linéaire.

---

1)Pourquoi la différence de temps de traitement de l'arraylist entre les deux opérations ?

2)Linkedlist est linéaire pour l'indexation, constante pour l'ajout à la fin, pourquoi ?

Answer 1

1) Parce que pour ajouter/supprimer au début, il faut tout déplacer et réindexer.

2) Parce qu'il maintient les références à la tête et à la queue (début et fin). Indexer signifie parcourir la liste.

Answer 2

I) ArrayList -> Il faut pousser tous les éléments d'une position en cas de suppression/addition au début, d'où un temps linéaire. A la fin du tableau, il suffit d'ajouter ou de supprimer.

ii)LinkedList -> Vous avez les références de la tête et de la queue, donc vous pouvez ajouter/supprimer n'importe quoi là (en temps constant).

Answer 3

1. Parce que la suppression à la fin ne nécessite pas de déplacer les données. Ajout de puede exiger une copie pour redimensionner la matrice de stockage, mais il est temps amorti .
2. Parce que l'ajout à la fin ne nécessite pas de parcourir la liste, mais l'indexation le fait.

Answer 4

Quand vous add à la fin d'un ArrayList il grandira tout seul pour avoir un peu de place. Donc, si vous avez un groupe de dix éléments ArrayList Si vous ajoutez un élément à la fin, il allouera en interne de l'espace pour vingt éléments, copiera les dix que vous aviez déjà, puis en ajoutera un. Ensuite, lorsque vous ajoutez un autre élément à la fin, il colle simplement ce douzième élément dans l'espace qu'il a déjà créé.

Cela ne lui confère pas techniquement une insertion à temps constant à la fin, mais cela lui donne amorti insertion à temps constant. En d'autres termes, sur un grand nombre d'opérations, le coût se rapproche du temps constant ; à chaque fois qu'il augmente, il double, de sorte que vous disposerez d'un nombre toujours plus grand d'insertions "gratuites" en temps constant avant de devoir à nouveau procéder à un "grow-and-copy".

Lorsque vous insérez au débutant il ne peut pas le faire et doit toujours copier la liste entière dans un nouvel emplacement (temps linéaire).

La suppression de la fin est toujours en temps constant car il suffit de faire passer la dernière cellule de "remplie" à "espace libre". Vous n'avez jamais besoin de copier la liste.

Quant à votre deuxième question, un LinkedList conserve un pointeur sur la fin de la liste, donc add y remove utilisent simplement ce pointeur et sont donc à temps constant. Il n'y a pas de pointeurs rapides au milieu de la liste, donc accéder à un élément arbitraire nécessite une traversée en temps linéaire du début à la fin (potentiellement).