为什么ArrayDeque比LinkedList更好

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

我很难看到有人在他们的代码中使用ArrayDeque。 如果有人对ArrayDeque的实现有更多的了解，这将会有所帮助。

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

Answer 1

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

如果你需要添加/删除两端，ArrayDeque显然比链表更好。 随机访问每个元素对于一个循环队列也是O（1）。

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

Answer 2

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

在某些情况下，“更好”是因为您没有为每个项目分配节点来插入; 相反，所有元素都存储在一个巨大的数组中，如果数组已满，则会resize。

Answer 3

我认为， LinkedList的主要性能瓶颈是，无论何时你推到任何一端的双端队列，实现都会分配一个新的链接列表节点，这个节点基本上涉及JVM / OS，而且这很贵。 而且，无论何时你从任何一端popup， LinkedList的内部节点都有资格进行垃圾回收，这是幕后的工作。

如果它可能是有趣的，我有一个certificate，添加一个元素ArrayList或ArrayDeque运行在amoritzed恒定时间; 参考这个 。

Answer 4

与使用O（1）访问元素的LinkedList相比，访问ArrayDeque中的元素总是更快。 在链接列表中，需要O（N）来查找最后一个元素。

ArrayDeque具有内存高效性，因为您不必跟踪链接列表中的下一个节点。

即使按照java文档，它已被引用

ArrayDeque是Deque接口的可resize的实现。 Array deques没有容量限制; 他们根据需要增长以支持使用。 他们不是线程安全的; 在没有外部同步的情况下，它们不支持multithreading的并发访问。 空元素是被禁止的。 当用作堆栈时，该类可能比Stack快，在用作队列时比LinkedList快。

这两个基准testingcertificateArrayDeque更快。

Answer 5

所有批评LinkedList的人，想想其他每个在Java中使用List的人大多数时候都会使用ArrayList和LinkedList ，因为他们已经在Java 6之前，并且因为这些人在大多数书籍中被教导为开始。

但是，这并不意味着，我会盲目地采取LinkedList或ArrayDeque的一面。 如果你想知道，请看一下Brian所做的以下基准testing。

testing设置考虑：

• 每个testing对象是500个字符的string。 每个string是内存中的一个不同的对象。
• 在testing过程中，testingarrays的大小将会变化。
• 对于每个arrays大小/队列实现组合，运行100个testing并计算平均每次testing时间。
• 每个testing包括为每个队列填充所有对象，然后将其全部删除。
• 以毫秒为单位测量时间。

testing结果：

• 在10000个以下的元素中，LinkedList和ArrayDequetesting平均在1 ms级别以下。
• 随着数据集越来越大，ArrayDeque和LinkedList平均testing时间之间的差异越来越大。
• 在testing大小为9,900,000个元素的情况下，LinkedList方法比ArrayDeque方法长约165％。

graphics：

带走：

• 如果您的要求是存储100或200个元素，则使用任何一个队列都不会有太大的区别。
• 但是，如果您正在开发移动设备，则可能需要使用具有最大容量的ArrayList或ArrayDeque ，因为严格的内存限制，该列表可能是必需的。
• 很多代码存在，使用LinkedList编写，所以在决定使用ArrayDeque时要ArrayDeque尤其是因为它没有实现List接口 （我认为这是足够大的原因）。 这可能是你的代码库广泛地与List接口进行交stream，最有可能的是你决定使用ArrayDeque 。 使用它的内部实现可能是一个好主意…

Answer 6

尽pipeArrayDeque<E>和LinkedList<E>都实现了Deque<E>接口，但ArrayDeque基本上使用了Object E[]来保存Object中的元素，因此它通常使用index来定位头部和尾部元素。

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

Answer 7

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