Java ListIterator 性能
我正在阅读关于 java ArrayList 和 LinkedList 性能的 线程。 Kevin Brock 先生的回答如下。
“链表添加并不总是 O(1) [或者这应该说 addLast() 是 O(1)]。 仅当从以下位置完成时，这才是正确的： 在 ListIterator 中。添加方法 在Java的LinkList实现中必须 搜索列表是否有添加 不在头部或尾部。”
我不明白他所说的“仅当通过 ListIterator 完成时”是什么意思。这是否意味着链表中存在一个数据结构，它保存每个索引的引用，并且一旦我们得到来自某个索引的列表迭代器，列表迭代器会立即返回，而无需遍历列表来查找该索引，
谢谢大家！
I was reading a thread here about the performance of java ArrayList and LinkedList. There is an answer from Mr Kevin Brock that reads the following.
"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."
I din't understand what he meant by "only if done through ListIterator". Does it mean there is a data structure within the linkedlist that holds the reference of each index and as soon as we get the listiterator from a certain index, listiterator is returned straight away without walking through the list to find that index?
Thanks guys!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这意味着迭代器直接指向列表节点；因此通过 get(int) 访问的时间复杂度为 O(N)，但 iterator.next() 的访问时间复杂度为 O(1)。后者有直接引用，不需要遍历任何东西；前者需要从列表的头部开始遍历。
It means that iterator points to list nodes directly; and so access via get(int) will be O(N), but iterator.next() wil be O(1). Latter has direct reference and does not need to traverse anything; former will need to traverse from head of the list.
如果添加到 ListIterator 指向的 LinkedList，则时间复杂度为 O(1)。这与添加到 LinkedList 的开头或 ArrayList 的结尾相同。
If you add to a LinkedList where the ListIterator is pointing to, it is O(1). This is the same as adding to the start of the LinkedList or the end of an ArrayList.
该注释引用了两个参数的 add 方法，[
add(int,E)][1]。假设线性分布的索引，那么这将是 O(n)，因为需要迭代列表才能找到适当的节点。它不适用于add(E)。[1]: http://download .oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)
The comment refers to the two argument add method, [
add(int,E)][1]. Assuming a linearly distributed index, then this will be O(n) as the list needs to be iterated through to find the appropriate node. It does not apply toadd(E).[1]: http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html#add(int, E)