217

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

我几乎看不到有人在他们的代码中使用 ArrayDeque。如果有人对 ArrayDeque 的实现方式有更多的了解，那将会很有帮助。

如果我理解它，我会更有信心使用它。我无法清楚地理解 JDK 实现管理头尾引用的方式。

4

9 回答 9

203

链接结构可能是迭代每个元素缓存未命中的最差结构。最重要的是，它们消耗更多的内存。

如果您需要添加/删除两端，ArrayDeque 明显优于链表。对于循环队列，随机访问每个元素也是 O(1)。

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

于 2011-05-28T17:23:34.073 回答
91

我认为主要的性能瓶颈LinkedList在于，每当您推送到双端队列的任何一端时，实现都会在后台分配一个新的链表节点，这本质上涉及 JVM/OS，而且成本很高。此外，无论何时从任何一端弹出，内部节点都LinkedList符合垃圾收集条件，这在幕后需要更多工作。此外，由于链表节点被分配在这里和那里，CPU缓存的使用不会提供太多好处。

如果它可能感兴趣，我有一个证据表明添加（附加）一个元素ArrayList或ArrayDeque在摊销的常数时间内运行；参考这个。

于 2015-09-17T07:46:09.463 回答
35

所有批评LinkedList, 想想其他在 Java 中使用过的人 List可能在大多数情况下都在使用ArrayList和 an LinkedList，因为他们在 Java 6 之前就已经使用了，而且因为这些是在大多数书籍中作为开始教授的内容。

但是，这并不意味着，我会盲目地站在LinkedList's 或ArrayDeque' 一边。如果您想知道，请查看以下由 Brian 完成的基准测试（存档）。

测试设置考虑：

  • 每个测试对象是一个 500 个字符的字符串。每个字符串都是内存中的不同对象。
  • 测试数组的大小将在测试期间发生变化。
  • 对于每个数组大小/队列实现组合，运行 100 次测试并计算平均每次测试时间。
  • 每个测试包括用所有对象填充每个队列，然后将它们全部删除。
  • 以毫秒为单位测量时间。

测试结果：

  • 在 10,000 个元素以下，LinkedList 和 ArrayDeque 测试的平均时间都在 1 毫秒以下。
  • 随着数据集变大，ArrayDeque 和 LinkedList 平均测试时间之间的差异也会变大。
  • 在 9,900,000 个元素的测试大小下，LinkedList 方法比 ArrayDeque 方法耗时约 165%。

图形：

在此处输入图像描述

带走：

  • 如果您的要求是存储 100 或 200 个元素，那么使用任何一个队列都不会产生太大的影响。
  • 但是，如果您在移动设备上进行开发，您可能希望使用 ArrayList或ArrayDeque估计由于严格的内存限制而可能需要列表的最大容量。
  • 存在很多代码，LinkedList在决定使用 a 时要谨慎编写，ArrayDeque尤其是因为它没有实现List接口（我认为这是足够大的原因）。可能是您的代码库与 List 接口进行了广泛的交流，很可能您决定使用ArrayDeque. 将它用于内部实现可能是一个好主意......
于 2017-06-20T17:34:47.223 回答
29

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

在某些情况下它“更好”，因为您没有为要插入的每个项目分配一个节点；取而代之的是，所有元素都存储在一个巨大的数组中，如果它满了就会调整大小。

于 2011-05-28T17:18:29.183 回答
21

ArrayDeque和LinkedList正在实现Deque接口，但实现方式不同。

主要区别：

  1. ArrayDeque类是Deque接口的可调整大小的数组实现， LinkedList类是列表实现

  2. NULL 元素可以添加到LinkedList但不能添加到ArrayDeque

  3. ArrayDeque比LinkedList在两端添加和删除操作更有效，而 LinkedList 实现在迭代过程中删除当前元素更有效

  4. LinkedList实现比ArrayDeque消耗更多的内存

所以如果你不必支持NULL元素&&寻找更少的内存&&两端添加/删除元素的效率，ArrayDeque是最好的

有关更多详细信息，请参阅文档。

于 2015-09-18T07:29:26.780 回答
1

虽然ArrayDeque<E>和LinkedList<E>都实现了 Deque<E>接口，但是 ArrayDeque 基本上使用 Object 数组E[]来将元素保存在其 Object 中，因此它通常使用索引来定位头和尾元素。

总之，它就像 Deque 一样工作（使用所有 Deque 的方法），但是使用数组的数据结构。至于哪个更好，取决于您使用它们的方式和位置。

于 2015-02-07T02:12:53.223 回答
1

我不认为ArrayDeque比LinkedList. 它们是不同的。

ArrayDeque比LinkedList平均速度快。但是对于添加一个元素，ArrayDeque需要摊销的常数时间，并且LinkedList需要常数时间。

对于需要所有操作都花费恒定时间的时间敏感型应用程序，LinkedList应该使用 only。

ArrayDeque的实现使用数组，需要调整大小，偶尔，当数组满了需要添加元素时，调整大小需要线性时间，导致该add()方法需要线性时间。如果应用程序对时间非常敏感，那可能是一场灾难。

有关 Java 实现这两种数据结构的更详细说明，请参阅由 Wayne 和 Sedgewick 教授的普林斯顿大学提供的 Coursera 上的“算法，第一部分”课程。该课程免费向公众开放。

详细信息在“第 2 周”的“堆栈和队列”部分的视频“调整数组大小”中进行了说明。

于 2021-11-16T18:08:37.073 回答
-1

情况并非总是如此。

例如，在下面的情况下linkedlist，性能比ArrayDeque根据 leetcode 103 更好。

/**
 * 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;
    }
}
于 2020-03-26T15:15:25.187 回答
-6

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

于 2015-09-21T07:02:09.013 回答