Java ListIterator 性能

Question

我正在读一篇thread这里介绍一下java ArrayList和LinkedList的性能。有来自Mr Kevin Brock的答复内容如下。

"Linked list add is not always O(1) [or this should say addLast() is O(1)]. This is only true if done from within a ListIterator. The add methods in Java's LinkList implementation must search through the list if additions are not on the head or tail."

我不明白他所说的“仅当通过ListIterator完成”是什么意思。这是否意味着链表中有一个数据结构保存每个索引的引用，一旦我们从某个索引获取列表迭代器，列表迭代器就会立即返回，而无需遍历列表来查找该索引？

谢谢大家!

Answer 1

表示迭代器直接指向列表节点；因此通过 get(int) 访问的时间复杂度为 O(N)，但 iterator.next() 的访问时间复杂度为 O(1)。后者有直接引用，不需要遍历任何东西；前者需要从列表的头部开始遍历。