是否對Java的LinkedList進行了優化，以便在必要時反向獲取（索引）？

我一直在努力優化LinkedList的一些方法。有誰知道Java默認雙鏈接LinkedList類是否被優化，以反向執行get()操作？例如：是否對Java的LinkedList進行了優化，以便在必要時反向獲取（索引）？

// Some LinkedList list that exists with n elements; 
int half = list.size()/2; 
list.get(half + 1);

會調用list.get(half + 1)，優化了搜走反向，因爲它是一個雙向鏈表？如果您知道元素位於列表的後半部分，則從最後進行搜索並轉到中心會更有意義。

我知道使用get(index)是O(n)時間，你應該在遍歷LinkedList時使用迭代器，但我只是好奇。

來源

2013-10-03 minhaz1

這是正確的，在的javadoc（第二段落的Java 7）第三段：'編索引的操作列表將從頭開始或結束時，取其更接近指定index.' – yshavit

只是遍歷列表注意從性能POV來看，無論如何，LinkedList的大部分用法都是錯誤的。 – maaartinus

是的。您可以自己檢查源代碼：http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%29

LinkedList#get(int)實現爲剛剛

return entry(index).element;

其中entry是一個私有方法。 entry的定義是：

private Entry<E> entry(int index) { 
    if (index < 0 || index >= size) 
     throw new IndexOutOfBoundsException("Index: "+index+ 
              ", Size: "+size); 
    Entry<E> e = header; 
    if (index < (size >> 1)) { 
     for (int i = 0; i <= index; i++) 
      e = e.next; 
    } else { 
     for (int i = size; i > index; i--) 
      e = e.previous; 
    } 
    return e; 
}

正如你可以看到，它結束時，如果指數比列表中點更大的倒計時。

來源

2013-10-03 06:02:23 jacobm

或者只是閱讀javadoc ... – assylias

是否對Java的LinkedList進行了優化，以便在必要時反向獲取（索引）？

回答

相關問題