Java ListIterator Performance

Question

Je lisais un thread ici à propos des performances de java ArrayList et LinkedList. Il y a une réponse de Mr Kevin Brock qui lit ce qui suit.

« add liste chaînée est pas toujours O (1) [ou cela devrait dire addLast() est O (1)]. Cela est vrai que si elle est faite à partir dans un ListIterator. L'add méthodes dans la mise en œuvre LinkList de Java doit rechercher dans la liste si les ajouts ne sont pas sur la tête ou la queue. "

Je ne comprends pas ce qu'il voulait dire par "seulement si c'est fait par ListIterator". Cela signifie-t-il qu'il y a une structure de données dans la liste liée qui contient la référence de chaque index et dès que nous obtenons le listiterator d'un certain index, listiterator est retourné immédiatement sans parcourir la liste pour trouver cet index?

Merci les gars!

Answer 1

Cela signifie que l'itérateur pointe vers la liste des nœuds directement; et donc l'accès via get (int) sera O (N), mais iterator.next() sera O (1). Ce dernier a une référence directe et n'a pas besoin de traverser quoi que ce soit; l'ancien devra traverser de la tête de la liste.

Answer 2

Si vous ajoutez à un LinkedList pointant vers le ListIterator, c'est O (1). Cela revient à ajouter au début de LinkedList ou à la fin d'une ArrayList.

Answer 3

Le commentaire fait référence à la méthode add à deux arguments, [add(int,E)] [1]. En supposant un index distribué linéairement, alors ce sera O (n) car la liste doit être itérée pour trouver le nœud approprié. Il ne s'applique pas à add(E).

[1]: http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)