为什么ArrayDeque比LinkedList好

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

我很少看到有人在代码中使用ArrayDeque。如果有人对ArrayDeque是如何实现的有更多的了解，这将是有帮助的。

如果我理解了它，我就会更有信心使用它。我不能清楚地理解JDK实现管理头部和尾部引用的方式。

110593 次浏览
小开

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

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

小开
最佳答案

链接结构可能是最糟糕的结构，因为每个元素都有缓存缺失。最重要的是，它们会消耗更多的内存。

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

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

小开

虽然ArrayDeque<E>和LinkedList<E>都实现了Deque<E>接口，但是ArrayDeque基本上使用对象数组E[]来保存对象中的元素，所以它通常使用索引来定位头部和尾部元素。

总之，它就像Deque一样工作(使用所有Deque的方法)，但是使用数组的数据结构。至于哪一个更好，取决于你如何和在哪里使用它们。

小开
我认为LinkedList中的主要性能瓶颈是这样一个事实，即无论何时你推到deque的任何端，在后台实现都会分配一个新的链表节点，这本质上涉及JVM/OS，这是昂贵的。此外，无论何时从任何一端弹出，LinkedList的内部节点都有资格进行垃圾收集，这是幕后的更多工作。 此外，由于链表节点分配在这里和那里，CPU缓存的使用不会提供太多的好处

如果可能感兴趣，我有一个证明，添加(追加)一个元素到ArrayList或ArrayDeque运行平摊常数时间;参考这。

小开

ArrayDeque和LinkedList实现了双端队列接口，但实现方式不同。

关键的不同点:

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

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

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

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

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

更多细节请参考文档。

小开

ArrayDeque访问一个元素的时间复杂度为O(1)， LinkList访问最后一个元素的时间复杂度为O(N)。ArrayDeque不是线程安全的，所以手动同步是必要的，这样你就可以通过多个线程访问它，这样它们会更快。

小开

所有批评LinkedList的人，想想其他在Java中使用List的人，大多数情况下可能使用ArrayList和LinkedList，因为他们在Java 6之前使用过，因为大多数书中都是作为开始教的。

但是，这并不意味着，我会盲目地站在LinkedList或ArrayDeque的一边。如果你想知道，看看下面的基准测试布莱恩(已存档)。

测试设置考虑:

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

测试结果:

  • 在10,000个元素以下，LinkedList和ArrayDeque测试的平均时间都低于1毫秒。
  • 随着数据集越来越大，ArrayDeque和LinkedList平均测试时间之间的差异也越来越大。
  • 在测试大小为9,900,000个元素时，LinkedList方法花费的时间比ArrayDeque方法长165%。

图:

enter image description here

导读:

  • 如果你的需求是存储100或200个元素，它不会使
    • 然而，如果你是在移动平台上开发，你可能想要使用一个 ArrayList或ArrayDeque，可以很好地猜测最大容量 该列表可能是由于严格的内存限制
  • 存在大量使用LinkedList编写的代码，所以在决定使用ArrayDeque时要小心，特别是因为它没有实现List接口(我认为这是足够大的原因)。可能是你的代码库与List接口进行了广泛的对话，最有可能的是你决定使用ArrayDeque。将它用于内部实现可能是个好主意……
小开

但情况并非总是如此。

例如，在下面的例子中，根据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;
}
}
小开

我不认为ArrayDeque比LinkedList好。他们是不同的。

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

对于时间敏感的应用程序，需要所有操作花费常数时间，应该只使用LinkedList。

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

关于Java实现这两种数据结构的更详细的解释可以在&;__abc0 &;普林斯顿大学在Coursera上提供的课程，由Wayne和Sedgewick教授。该课程对公众免费开放。

详细内容在视频" Resizing array "在“堆栈和队列”中;“第二周”的部分。


提交答案