为什么ArrayDeque比LinkedList更好

java linked-list deque arraydeque

2022-08-31 05:48:55

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

我几乎看不到有人在他们的代码中使用ArrayDeque。如果有人能更深入地了解 ArrayDeque 是如何实现的，那将是有帮助的。

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

答案 1

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

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

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

答案 2

我认为，主要的性能瓶颈在于，每当您推送到 deque 的任何一端时，在幕后，实现都会分配一个新的链表节点，该节点本质上涉及 JVM/OS，而且成本很高。此外，每当您从任何一端弹出时，的内部节点都有资格进行垃圾回收，这在幕后需要做更多的工作。此外，由于链接列表节点是在这里和那里分配的，因此CPU缓存的使用不会带来太多好处。LinkedListLinkedList

如果它可能很有趣，我有一个证明，添加（追加）一个元素到或以摊销常量时间运行;请参考这个。ArrayListArrayDeque