为什么ArrayDeque比LinkedList更好？

Question

我试图了解为什么Java的ArrayDeque比Java的LinkedList更好，因为它们都实现了Deque接口。

我几乎没有看到有人在他们的代码中使用ArrayDeque。如果有人能更详细地介绍一下ArrayDeque的实现方式，那将会很有帮助。

如果我理解了它，我将更加自信地使用它。我无法清楚地理解JDK实现的头和尾引用管理方式。

- Cruel

---

请看我几天前回答此问题的答案：https://dev59.com/Km025IYBdhLWcg3wPzbL - Renato Dinhani

在你的jdk安装文件夹中，有一个名为src.zip的文件。它是Java类源代码的归档文件。我强烈建议您学习这些类的结构和内部机制，以更好地理解Java类的工作原理。 - user784540

还有一点需要注意。ArrayDeque 的默认大小为 16。当 ArrayDeque 充满时，它会将其大小加倍。在大小加倍后，元素将被复制到新数组中。最好使用初始大小初始化 ArrayDeque。 - Vineeth Chitteti

另一个值得一提的点是，在LinkedList中，您可以使用索引来迭代其元素，而ArrayDeque不支持基于索引的访问。 - Java Main

Answer 1

链式结构在每个元素缺失缓存的情况下可能是最糟糕的迭代结构。此外，它们消耗的内存要多得多。

如果需要在两端进行添加/删除操作，则ArrayDeque比链表显着更好。对于循环队列，每个元素的随机访问也是O(1)。

链表唯一更好的操作是在迭代期间删除当前元素。

- bestsss

---

需要翻译的内容：Another difference to bear in mind: LinkedList supports null elements, whereas ArrayDeque does not.另一个需要注意的区别是：LinkedList支持空元素，而ArrayDeque不支持。 - Luke Usherwood

另一个小缺点（对于实时应用程序）是，在推入/添加操作中，当ArrayDeque的内部数组已满时，需要花费更多时间，因为它必须将其大小加倍并复制所有数据。 - V G

@AndreiI，这只是故事的一面。即使您排除了实时应用程序的迭代成本和预分配所需容量的能力，垃圾回收器可能仍需要迭代整个LinkedList。基本上，您正在将成本（而且这些成本更高）移到了GC中。 - bestsss

因为涉及到被释放节点的垃圾回收成本，赋值头节点可能还需要进行卡片标记（如果LinkedList已经在tenured gen中，则需要再次进行GC）...这还要加上额外的间接性（缓存未命中）才能返回元素并重新连接。 - bestsss

同时，“LinkedList” 实现了“List”，而 “ArrayDeque” 没有。这意味着“LinkedList” 有诸如“indexOf”或“remove(int)”之类的方法，而“ArrayDeque”没有。这在某些情况下可能很重要。 - ZhekaKozlov

Answer 2

我认为LinkedList的主要性能瓶颈在于每次推入双端队列的任何一端时，实现都会在后台分配一个新的链表节点，这实际上涉及到JVM/OS，因此代价高昂。此外，每当您从任何一端弹出时，LinkedList的内部节点就变得适合进行垃圾回收，这是更多的后台工作。同样，由于链表节点在这里和那里被分配，使用CPU缓存不会提供太多好处。

如果感兴趣的话，我有一个证明，证明将元素添加（追加）到ArrayList或ArrayDeque中的摊销常数时间运行；请参阅这个链接。

- coderodde

---

在链表和数组中，如何从头部添加/移除元素更好呢？相比于 ArrayDeque 中需要移动多个元素，链表只需要改变与 prev 和 next 相关的引用。因此，链表应该具有更大的优势。 - Stefan

Answer 3

所有批评 LinkedList 的人，请想想其他使用 Java 中的 List 的人，他们很可能大部分时间使用的是 ArrayList 和 LinkedList，因为它们出现在 Java 6 之前，并且它们是大多数书籍中作为开始教学的内容。但是，这并不意味着我盲目地支持 LinkedList 或 ArrayDeque。如果你想知道，可以查看下面 由 Brian 完成的 基准测试（已存档）。

测试设置考虑到：

每个测试对象都是一个 500 字符的字符串。每个字符串在内存中都是不同的对象。

测试数组的大小将在测试过程中变化。

对于每个数组大小/队列实现组合，运行 100 次测试并计算每次测试的平均时间。

每个测试都包括填充每个队列的所有对象，然后删除它们全部。

以毫秒为单位测量时间。

测试结果：

• 在10000个元素以下的情况下，LinkedList和ArrayDeque的测试平均时间都在1毫秒以下。
• 随着数据集变得更大，ArrayDeque和LinkedList的平均测试时间差异越来越大。
• 在测试大小为9900000个元素时，LinkedList方法所用时间比ArrayDeque方法长了约165％。

图表：

要点：

• 如果您的需求是存储100或200个元素，使用任何一种队列都不会有太大区别。
• 然而，如果您正在开发移动应用程序，您可能需要使用一个ArrayList或ArrayDeque，并且需要对列表可能需要的最大容量进行良好的猜测，因为内存受到严格限制。
• 许多代码使用LinkedList编写，因此在决定使用ArrayDeque时要小心，特别是因为它没有实现List接口（我认为这已经足够重要了）。您的代码库可能与List接口广泛交互，因此您决定使用ArrayDeque。将其用于内部实现可能是一个好主意...

- Manish Kumar Sharma

---

这个基准测试如何捕获由链表垃圾回收引起的GC时间？ - 0xbe5077ed

Answer 4

ArrayDeque和LinkedList都实现了Deque接口，但实现方式不同。

更多详情请参考Oracle文档。

主要区别：

1. ArrayDeque类是Deque接口的可调整大小的数组实现，而LinkedList类则是列表实现
2. 可以向LinkedList中添加NULL元素，但不能向ArrayDeque中添加
3. ArrayDeque在两端添加和删除操作方面比LinkedList更有效率，而LinkedList实现在迭代期间删除当前元素非常高效
4. LinkedList的实现消耗比ArrayDeque更多的内存

因此，如果您不需要支持NULL元素，并且希望占用更少的内存并具有在两端添加/删除元素的效率，则ArrayDeque是最佳选择。

- Ravindra babu

---

“在链表中，要查找最后一个元素需要 O(N) 的时间复杂度”这句话并不完全正确。链表通常是作为双向链表实现的，因此您无需遍历整个链表即可获取最后一个元素(header.previous.element)。此外，“内存效率”的说法也可能受到挑战，因为支持链表的数组大小总是会被调整为下一个 2 的幂次方。 - Clément MATHIEU

“找到最后一个元素需要O(N)”是错误的。链表保留有对最后一个节点的引用，而LinkedList.descendingIterator()可以获取该节点。因此，我们可以获得O(1)的性能。请参见：https://coffeeorientedprogramming.wordpress.com/2018/04/23/linkedlist-descendingiterator-run-time/（因此进行了反对投票）。 - Leo Ufimtsev

当您使用Iterator访问最后一个元素时，对于这两个类，操作的时间复杂度都是O(N)。当您使用常见的Deque接口时，对于这两个类，访问最后一个元素的时间复杂度都是O(1)。无论您采取哪种观点，同时将O(1)归因于ArrayDeque和O(N)归因于LinkedList都是错误的。 - Holger

所有的建议都被采纳并修正了内容。 - Ravindra babu

Answer 5

ArrayDeque是Java 6中新增的，这就是为什么很多代码（特别是试图与早期Java版本兼容的项目）不使用它的原因。

在某些情况下，它比较“好”，因为您不需要为要插入的每个项分配一个节点；相反，所有元素都存储在一个巨大的数组中，如果该数组已满，则会调整大小。

- C. K. Young

Answer 6

我认为ArrayDeque并不比LinkedList更好。它们是不同的。

平均而言，ArrayDeque比LinkedList更快。但是对于添加元素，ArrayDeque需要摊销常数时间，而LinkedList则需要常数时间。

对于那些需要所有操作都需要花费常数时间的时效性应用程序，只能使用LinkedList。 ArrayDeque的实现使用数组，并需要进行调整大小。当数组已满且需要添加元素时，需要花费线性时间来调整大小，从而导致add()方法花费线性时间。如果应用程序非常时间敏感，那将是一场灾难。

Java实现这两种数据结构的更详细说明可在普林斯顿大学所提供的Coursera的“Algorithms, Part I”课程中找到。该课程免费向公众开放。

详细信息请参见“第2周”中“栈和队列”部分的“调整大小数组”视频。

- anjiez

Answer 7

尽管 ArrayDeque<E> 和 LinkedList<E> 都实现了 Deque<E> 接口，但是 ArrayDeque 基本上使用对象数组 E[] 来保存其内部元素，因此通常使用索引来定位头和尾元素。

总之，它就像 Deque 一样工作（具有所有 Deque 的方法），但使用数组的数据结构。至于哪种更好，取决于您如何以及在哪里使用它们。

- rekinyz

Answer 8

我不确定ArrayDeque是如何实现的，但是我几年前在C++中实现了类似的东西，我非常确定它们是一样的。 这个集合实际上是一个被认为是“循环”的ArrayList，也就是说，在a[n-1]之后的下一个项目是a[0]。 deque还保持两个指针（整数）指向deque中的第一个和最后一个项目。当你使用addFirst时，你会减少“first”（循环），当你使用addLast时，你会增加“last”。这非常简单和高效。

- ModdyFire

Answer 9

这并不总是如此。

例如，在下面的情况中，根据leetcode 103，linkedlist 的性能优于ArrayDeque。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> rs=new ArrayList<>();
        if(root==null)
            return rs;
        //  here ,linkedlist works better
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        boolean left2right=true;
        while(!queue.isEmpty())
        {
            int size=queue.size();
            LinkedList<Integer> t=new LinkedList<>();
            while(size-->0)
            {
                TreeNode tree=queue.remove();
                if(left2right)  
                    t.add(tree.val);
                else
                    t.addFirst(tree.val);
                if(tree.left!=null)
                {
                    queue.add(tree.left);
                }
                if(tree.right!=null)
                {
                    queue.add(tree.right);
                }
            }
            rs.add(t);
            left2right=!left2right;
        }
        return rs;
    }
}

- Red

Answer 10

ArrayDeque 访问元素的时间复杂度为 O(1)，而 LinkList 访问最后一个元素的时间复杂度为 O(N)。ArrayDeque 不是线程安全的，因此需要手动同步以便通过多个线程访问它并使其更快。

- Piyush Yawalkar

---

如果您在Java的“Collection”中提到“LinkedList”，它是双向链表，并且可以快速访问头部和尾部，因此也可以在O(1)时间内访问最后一个元素。 - Maurice

访问LinkedList中的最后一个元素不是O(N)。如果使用descendingIterator()，则可以在O(1)中执行。请参见https://coffeeorientedprogramming.wordpress.com/2018/04/23/linkedlist-descendingiterator-run-time/（因此被downvote）。 - Leo Ufimtsev

这两个类都不是线程安全的。而且句子开头的“手动同步是必要的”和结尾的“它们更快”之间没有任何关联。 - Holger