列表實現：LinkedList真的表現如此糟糕與ArrayList和TreeList？

Question

從Apache TreeList doc摘自：

下相對錶現的統計數據表明這種 類：

   get add insert iterate remove 
TreeList  3 5  1  2  1 
ArrayList  1 1  40  1  40 
LinkedList 5800 1  350  2  325 

它接着說：

LinkedList很少是很好的實施選擇。 TreeList幾乎總是一個很好的替代品，儘管它確實使用了更多的內存。

我的問題是：

• 什麼是與ArrayListadd， insert和remove次破碎 LinkedList？我們應該期望，對於 之一，那真實世界插入和刪除案件 大大青睞ArrayList？

• 難道這TreeList只是把釘子放在古老的LinkedList的棺材？

我傾向於認爲他們已經攤銷或忽略ArrayList的成長的煩惱，並且在已經位於LinkedList尚未考慮插入和移除時間的項目。

Answer 1

這裏的關鍵是三個List實現中插入/刪除操作的複雜性。 ArrayList對於任意索引具有O（n）的插入/刪除時間，但如果操作位於列表的末尾，則爲O（1）。 ArrayList對任何位置都有O（1）訪問的便利。 LinkedList類似於O（n），但對於任意位置的列表（開始和結束）和O（n）訪問的任一端的操作，O（1）是O（1）。 TreeList對於任何位置的所有操作都具有O（logn）複雜性。

這清楚地表明TreeList對於足夠大的列表來說更快，只要在任意位置上進行插入/刪除。但是AFAIK，TreeLists被實現爲一個二叉搜索樹，並且具有與其O（logn）操作相關的更大的常量，而ArrayLists的相似操作僅僅是數組的封裝。這使得TreeList對於小列表實際上更慢。另外，如果你所做的只是把元素附加到List中，那麼ArrayList/LinkedList的O（1）性能顯然更快。而且，插入/刪除的次數通常比訪問次數少得多，這在很多情況下傾向於使ArrayList總體上更快。 LinkedList在列表兩端的常量時間插入/刪除使得實現Queues，Stacks和Deques等數據結構的速度更快。

在一天結束時，這一切都取決於你需要一個列表。沒有一種萬能的解決方案。您必須選擇最適合您工作的實施。

Answer 2

這是由於這些集合背後的data structures。 TreeList是tree，它允許相對較快的讀取，插入，刪除（全O（log n））。 ArrayList使用array來存儲數據，所以當您插入或刪除數據時，陣列中的每個項目都必須向上或向下移動（最壞情況是O（n））。數組的大小也是固定的，所以如果它溢出當前數組的容量，則必須創建一個新的較大的數組（通常是最後一個數組的兩倍，以保持最小大小）。 LinkedList使用...一個linked list。鏈表通常會引用列表中的第一個（有時是最後一個）元素。然後，列表中的每個元素都會引用列表中的下一個元素（對於單鏈表）或下一個元素和上一個元素（對於雙鏈表）。因此，要訪問某個特定元素，必須遍歷每個元素才能到達那裏（O（n）最壞的情況）。當插入或刪除特定元素時，您必須找到插入或移除特定元素的位置，這需要時間（O（n）最差的情況）。然而，簡單地將另一個元素添加到開始或結束（O（1））的成本非常低。

有關於數據結構的完整書籍，以及何時使用它們，我建議您閱讀更基本的書籍。

Answer 3

因爲鏈表必須逐節點瀏覽以獲取列表中的任何位置（根據實現情況保存前端或後端），因此這些數字非常高。

爲了在一個大的LinkedList中添加/插入/刪除，你需要從節點到節點進行大量的跳轉才能到達正確的位置。

如果他們讓適當大小的ArrayList開始，那麼成長的痛苦將不會是什麼。如果ArrayList很小，那麼成長的痛苦並不重要。

對於LinkedList，如果操作都在列表的前面，那麼如果它們在最後，它的影響會小得多。

你應該做的是始終使用接口，例如：List當聲明變量和參數時，你可以改變「new LinkedList（）;」到「new ArrayList（）;」並剖析代碼以瞭解它在特定代碼中的表現。

由於無需從節點跳到節點，我總是默認爲ArrayList而不是LinkedList。

我相信樹列表將比兩者都快很多（即使不查看代碼）。樹被設計得很快。

Answer 4

對於ArrayList，由於它不經常進行，所以基本上可以忽略該成本。如果它實際上是一個問題，那麼只需將數組放大就可以開始。

如果我有一個小列表，那麼一個LinkedList是有意義的，因爲在這一點上有最小的好處。如果列表將會很長，那麼顯然TreeList更有意義。

如果我要對列表進行大量的隨機訪問，那麼ArrayList更有意義。

要使用哪個容器取決於您將使用哪種容器。沒有一個正確的容器，因爲每個容器都有自己的優勢和弱點，並且有了經驗，你就開始瞭解何時使用哪個容器。

Answer 5

每個在這裏回答的人都是正確的。他們都認爲他們的觀點是正確的，這很大程度上取決於你的使用模式，即沒有一個通用的列表。但是在寫作的那一刻，當LinkedList處於最佳狀態時，他們都忘記提及（或者說，或者我是草率的閱讀器）用例：迭代器定位插入。這意味着，如果你正在做不只是

LinkedList::add(int index, E element) 
      Inserts the specified element at the specified position in this list. 

這似乎是他們曾經獲得的統計方法，但

iterator.insert(E element) 

通過兩種

public abstract ListIterator<E> listIterator(int index) 
Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list. 

獲得 iterator

或

public Iterator<E> iterator() 
Returns an iterator over the elements in this list (in proper sequence). 

，那麼你一定會得到最好的任意插入性能。這意味着你可以限制對iterator（）和listIterator（）的調用次數，以及遍歷列表中迭代器的移動次數（例如，你只需要在列表中做一個順序遍歷來完成你需要的所有插入操作）。這使得它的用例在數量上非常有限，但它們卻是非常頻繁出現的用例。而LinkedList在其中的表現就是爲什麼它將會保留在所有語言的所有容器集合中，而不僅僅是Java。

PS。上述所有過程當然適用於所有其他操作，如get（），remove（）等。通過迭代器精心設計的訪問將使所有這些操作都具有非常小的實際常量O（1）。當然，對於所有其他列表也可以這樣說，即迭代器訪問會加快它們的速度（無論如何略微）。但不是ArrayList的insert（）和remove（） - 它們仍然是O（n）...而不是TreeList的insert（）和remove（） - 樹平衡開銷並不是你可以避免的...並且TreeList可能有更多的內存開銷...你明白我的想法。綜上所述，LinkedList適用於列表中的小型高性能掃描類操作。無論這是否是您需要的用例 - 只有您可以告訴。

PSS。這就是說，因此我也仍然

傾向於認爲他們有 攤銷或忽略的ArrayList的 成長的煩惱，並沒有考慮到 考慮插入和 去除次項目的 LinkedList的是已經被定位爲 。

Answer 6

請注意，ArrayList通常比LinkedList快，即使您的代碼只調用兩個常量時間的方法。例如，當不需要調整大小時，ArrayList.add（）簡化拷貝單個變量並增加計數器，而LinkedList.add（）也必須創建節點並設置多個指針。另外，LinkedList節點需要更多內存，這會減慢應用程序的運行速度，垃圾收集必須處理節點。

如果需要添加或刪除列表中的任一端的元素，但不需要隨機訪問，一個ArrayDeque率比在LinkedList快，但它需要Java 6

一個LinkedList意義用於迭代整個列表，然後添加或刪除中間的元素，但這是一種不尋常的情況。