Java ListIterator性能

Question

我在这里读到了一个关于java、ArrayList和LinkedList性能的ArrayList。Mr Kevin Brock给出的答案如下所示。

“链接列表添加不一定是O(1)，或者这应该说addLast()是O(1)。只有在ListIterator中进行添加才是正确的。如果没有添加，则LinkList实现中的添加方法必须在列表中搜索。”

我不明白他所说的“只有通过ListIterator完成”是什么意思。这是否意味着链接列表中有一个数据结构，它保存了每个索引的引用，并且当我们从某个索引中获得listiterator时，listiterator就会立即返回，而不需要遍历列表来查找该索引？

谢谢你们！

Answer 1

这意味着迭代器直接指向列表节点；因此通过get(int)访问将是O(N)，但是iterator.next()将是O(1)。后者有直接的参考，不需要遍历任何东西；前者将需要从列表的头遍历。

Answer 2

如果将LinkedList添加到ListIterator所指向的位置，则为O(1)。这与添加到LinkedList的开始或ArrayList的末尾相同。

Answer 3

注释引用了两个参数add方法，add(int,E)。假设一个线性分布的索引，那么这将是O(n)，因为列表需要迭代以找到适当的节点。它不适用于add(E)。

1：http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int