Java ListIterator性能

我在這裏讀了一個thread關於java ArrayList和LinkedList的性能。從Mr Kevin Brock有一個答案，讀取以下內容。Java ListIterator性能

「鏈接列表添加並不總是O（1） [或這應該說addlast僅（）是 O（1）]。如果從一個的ListIterator內完成這僅僅是真實的。該插件Java的LinkList實現中的方法必須在列表中搜索，如果添加的不在頭部或尾部。

我不明白他的意思是「只有通過ListIterator完成」。這是否意味着鏈表中有一個數據結構，它包含每個索引的引用，並且只要我們從某個索引獲取列表引用者，listiterator會立即返回，而無需遍歷列表以找到該索引？

謝謝你們！

2010-12-12 Abidi

這意味着迭代器直接指向列表節點;所以通過get（int）訪問將是O（N），但iterator.next（）將是O（1）。後者有直接的參考，不需要遍歷任何東西;前者需要從列表頭開始遍歷。

2010-12-12 19:00:37 StaxMan

感謝您的及時答覆斯塔克斯曼。那麼這是否意味着ListIterator與「鏈表」並行維護以保存節點的引用？ – Abidi 2010-12-12 19:11:27

@Aididi，是的。不過，我懷疑你正在做什麼可以更有效率地做另一種方式。通常，還有另一種方法可以完成需要完成的任務，因此您不必將隨機地址插入列表中。 – 2010-12-12 19:15:23

@彼得，謝謝你的回答。 – Abidi 2010-12-12 19:23:09

如果添加到ListIterator指向的LinkedList，則它是O（1）。這與添加到LinkedList的開始或ArrayList的結尾相同。

2010-12-12 19:01:09

評論指的是兩個參數添加方法[add(int,E)] [1]。假設線性分佈索引，那麼這將是O（n），因爲列表需要迭代以找到適當的節點。它不適用於add(E)。

2010-12-12 21:19:42

回答