爲什麼ArrayDeque比LinkedList更好

我想了解爲什麼Java的ArrayDeque比Java的LinkedList更好，因爲它們都實現了Deque接口。爲什麼ArrayDeque比LinkedList更好

我幾乎沒有看到有人在他們的代碼中使用ArrayDeque。如果有人對ArrayDeque的實現方式有更多的瞭解，這將有所幫助。

如果我明白了，我會更有信心使用它。我無法清楚地理解JDK的實現方式，因爲它管理頭部和尾部引用的方式。

2011-05-28 Cruel

看看這個問題我在幾天前做的答案：http://stackoverflow.com/questions/6129805/what-is-the-fastest- java-collection-with-the-the-basic-functional-of-a-queue – 2011-05-28 17:19:22

在你安裝了jdk的文件夾中有一個'src.zip'文件。它是帶有java類源代碼的存檔。我強烈建議研究這些類的結構和內部，以更好地理解java類如何工作。 – 2015-09-17 07:50:09

鏈接結構可能是每個元素上緩存未命中迭代的最糟糕的結構。最重要的是，它們消耗更多的內存。

如果你需要添加/刪除兩端，ArrayDeque顯然比鏈表更好。隨機訪問每個元素對於循環隊列也是O（1）。

鏈接列表的唯一更好的操作是在迭代期間刪除當前元素。

來源

2011-05-28 17:23:34 bestsss

+20

要記住的另一個區別是：LinkedList支持null元素，而ArrayDeque則不支持。 – 2013-07-10 17:24:40

另一個小缺點（對於實時應用程序）是在推/加操作時，ArrayDeque的內部數組已滿時需要多一點，因爲它必須將其大小加倍並複製所有數據。 – 2013-09-13 15:35:45

@AndreiI，這只是故事的一面。即使排除實時應用程序的迭代成本和預先分配所需容量的能力，GC也可能需要迭代整個LinkedList。基本上你將成本（更高的啓動）轉移到GC中。 – bestsss 2014-05-19 05:26:59

ArrayDeque是Java 6的新增功能，這就是爲什麼很多代碼（特別是試圖與早期Java版本兼容的項目）不使用它。

在某些情況下它會「更好」，因爲您沒有爲要插入的每個項目分配節點;相反，所有元素都存儲在一個巨大的數組中，如果數組已滿，則會調整其大小。

來源

2011-05-28 17:18:29

雖然ArrayDeque<E>和LinkedList<E>兼得實施Deque<E>接口，但ArrayDeque使用基本上對象陣列E[]用於保持它的對象內部的元素，所以它通常使用索引用於定位頭部和尾部元件。

總而言之，它只是像Deque一樣工作（使用Deque的所有方法），但是使用數組的數據結構。至於哪一個更好，取決於你如何以及在哪裏使用它們。

來源

2015-02-07 02:12:53 rekinyz

我相信LinkedList中的主要性能瓶頸是，無論何時您推送到雙端隊列的任何一端，實現都會分配一個新的鏈接列表節點，這實際上涉及到JVM/OS，而且這很貴。此外，無論何時從任何一端彈出，內部節點LinkedList都有資格進行垃圾回收，這是幕後的更多工作。

如果它可能是有趣的，我有一個證明，ArrayList或ArrayDeque添加一個元素運行在amoritzed恆定時間;請參閱this。

來源

2015-09-17 07:46:09 coderodde

與具有O（1）訪問元素的LinkedList相比，訪問ArrayDeque中的元素總是更快。在鏈接列表中，需要O（N）來查找最後一個元素。

ArrayDeque具有內存效率，因爲您不必跟蹤鏈接列表中的下一個節點。

即使每Java文檔，已經引用了這

ArrayDeque是雙端隊列接口的大小可變數組實現。Array deques沒有容量限制;它們根據需要增長以支持使用。它們不是線程安全的;在沒有外部同步的情況下，它們不支持多線程的併發訪問。禁止使用空元素。當用作堆棧時，該類可能比Stack快，並且在用作隊列時比LinkedList快。

Benchmarking這兩個證明ArrayDeque更快。

來源

2015-09-18 07:29:26

「在鏈接列表中，需要O（N）來查找最後一個元素。」並不完全正確。 LinkedList被實現爲雙向鏈表，因此您不必遍歷列表以獲取最後一個元素（'header.previous.element'）。「內存效率」聲明也可能受到挑戰，因爲支持數組總是調整爲下一個2的冪。 – 2015-09-21 16:06:21

-1

ArrayDeque訪問元素的時間複雜度爲O（1），LinkList的訪問時間爲O（N）以訪問最後一個元素。 ArrayDeque不是線程安全的，所以手動同步是必需的，這樣你就可以通過多線程訪問它，所以它們更快。

來源

2015-09-21 07:02:09

如果您引用Java的「集合」中的LinkedList，則它是雙重鏈接的並且可以快速訪問頭部和尾巴，所以訪問最後一個元素也需要O（1）。 – Maurice 2016-07-15 19:34:50

所有的人都在批評LinkedList，想想已經使用List在Java中可能使用ArrayList和所有其他人的LinkedList大部分的時間，因爲他們一直在Java 6的前後，因爲這些都是那些被教導的從大多數書籍開始。

但是，這並不意味着，我會盲目地採取LinkedList的或ArrayDeque的一面。如果你想知道，看看下面的基準done by Brian。

測試設置認爲：

每個測試對象是500字符串。每個字符串是內存中的一個不同的對象。

在測試過程中，測試陣列的大小會有所不同。

對於每個陣列大小/隊列實現組合，運行100個測試並計算平均每次測試時間。

每個測試包括爲每個隊列填充所有對象，然後全部刪除它們。

以毫秒爲單位的測量時間。

測試結果：

低於10000元，LinkedList的和ArrayDeque測試都平均爲子1 ms級。

隨着數據集變大，ArrayDeque和LinkedList平均測試時間之間的差異變大。

在9,900,000個元素的測試規模下，LinkedList方法比ArrayDeque方法花費了〜165％的時間。

圖：

外賣：

如果您的要求存儲100點或200的元素，它不會使用make 多大的差別隊列中的任何一個。
但是，如果您正在開發移動設備，則可能需要使用 ArrayList或ArrayDeque，並且最大容量爲，因爲嚴格的內存限制可能需要該列表。
大量的代碼存在，使用LinkedList所以小心行事決定使用ArrayDeque特別是因爲它沒有實現List接口寫的時候（我認爲這是原因足夠大）。這可能是因爲你的代碼庫廣泛地與List接口對話，很可能你決定加入ArrayDeque。使用它的內部實現可能是一個好主意...

來源

2017-06-20 17:34:47

該基準測試如何捕獲由鏈表垃圾引起的GC時間？ – 0xbe5077ed 2017-07-06 17:04:32

爲什麼ArrayDeque比LinkedList更好

回答

相關問題