我正在读一篇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完成”是什么意思。这是否意味着链表中有一个数据结构保存每个索引的引用，一旦我们从某个索引获取列表迭代器，列表迭代器就会立即返回，而无需遍历列表来查找该索引？
谢谢大家!
最佳答案
表示迭代器直接指向列表节点；因此通过 get(int) 访问的时间复杂度为 O(N)，但 iterator.next() 的访问时间复杂度为 O(1)。后者有直接引用，不需要遍历任何东西；前者需要从列表的头部开始遍历。
关于Java ListIterator 性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4423381/