为什么ArrayDeque比LinkedList更好
Cru*_*uel 141 java linked-list deque arraydeque
我试图理解为什么Java的ArrayDeque优于Java的LinkedList,因为它们都实现了Deque接口.
我几乎没有看到有人在他们的代码中使用ArrayDeque.如果有人对ArrayDeque的实现方式有了更多了解,那将会很有帮助.
如果我明白了,我会更有信心使用它.我无法清楚地了解JDK实现它管理头尾引用的方式.
bes*_*sss 139
链接结构可能是在每个元素上以高速缓存未命中进行迭代的最差结构.除此之外,它们消耗更多的内存.
如果需要添加/删除两端,ArrayDeque明显优于链表.随机访问每个元素对于循环队列也是O(1).
链表的唯一更好的操作是在迭代期间删除当前元素.
- 要记住的另一个区别是:LinkedList支持null元素,而ArrayDeque则不支持. (45认同)
- 另一个小缺点(对于实时应用程序)是在推送/添加操作时,当ArrayDeque的内部数组已满时需要更多,因为它必须将其大小加倍并复制所有数据. (12认同)
- 另外，“LinkedList”实现了“List”，而“ArrayDeque”则没有。这意味着“LinkedList”具有“indexOf”或“remove(int)”等方法，而“ArrayDeque”则没有。有时它可能很重要。 (7认同)
- @AndreiI,这只是故事的一个方面.即使您排除实时应用程序的迭代成本和预分配所需容量的能力,GC也可能需要迭代整个LinkedList.基本上,您正在将成本(更高的启动时间)转移到GC中. (4认同)
- @DavidT.b/c它涉及释放节点的GC成本,分配头也可能需要卡标记(如果LinkedList已经在tenured gen中,则再次为GC)......并且这是在额外间接的基础上(缓存 - miss)返回元素并重新链接. (3认同)
cod*_*dde 52
我认为主要的性能瓶颈LinkedList在于,无论何时推送到deque的任何一端,在场景后面,实现都会分配一个新的链表节点,这实际上涉及JVM/OS,而且价格昂贵.此外,无论何时从任何一端弹出,内部节点都有LinkedList资格进行垃圾收集,这是场景背后的更多工作.此外,由于链接列表节点是在这里和那里分配的,因此使用CPU缓存不会带来太多好处.
如果它可能是有意义的,我有一个证据,即在摊还的常数时间内添加一个元素ArrayList或以其ArrayDeque运行; 参考这个.
- 你能告诉我在链接中添加/删除头部元素比在数组中更好吗？难道 LinkedList 不应该具有优势吗？因为仅更改对“prev”和“next”的引用，而在 ArrayDeque 中许多元素需要移动？ (5认同)
Chr*_*ung 25
ArrayDeque Java 6是新的,这就是为什么许多代码(特别是试图与早期Java版本兼容的项目)不使用它.
在某些情况下,它"更好",因为您没有为每个要插入的项目分配节点; 相反,所有元素都存储在一个巨大的数组中,如果它已满,则会调整大小.
Rav*_*abu 14
与使用O(1)的LinkedList访问元素相比,访问ArrayDeque中的元素总是更快.在链接列表中,需要O(N)才能找到最后一个元素.
ArrayDeque是内存高效的,因为您不必跟踪链接列表中的下一个节点.
即使按照java文档,它也被引用了
ArrayDeque是Deque接口的Resizable-array实现.阵列deques没有容量限制; 他们根据需要增长以支持使用.它们不是线程安全的; 在没有外部同步的情况下,它们不支持多线程的并发访问.禁止使用空元素.当用作堆栈时,此类可能比Stack快,并且当用作队列时比LinkedList更快.
这两个基准测试证明ArrayDeque更快.
- "在链接列表中,需要O(N)才能找到最后一个元素." 事实并非如此.LinkedList实现为双向链表,因此您不必遍历列表以获取最后一个元素(`header.previous.element`)."内存效率"声明也可能受到挑战,因为后备阵列始终调整为下一个2的幂. (14认同)
- "需要O(N)才能找到最后一个元素"是错误的.链接列表保留对最后一个节点的引用,LinkedList.descendingIterator()获取该节点.所以我们获得了O(1)的表现.请参阅:https://coffeeorientedprogramming.wordpress.com/2018/04/23/linkedlist-descendingiterator-run-time/(因此downvoting). (5认同)
pul*_*ion 13
所有批评a的人LinkedList,想想List在Java中使用过的所有其他人 可能会使用ArrayList和LinkedList大多数时间,因为他们已经在Java 6之前,因为那些是在大多数书籍中被教导的开始.
但是,这并不意味着,我会盲目地采取LinkedList或支持ArrayDeque.如果你想知道,请看看Brian完成的以下基准测试.
测试设置考虑:
- 每个测试对象都是500个字符的字符串.每个String都是内存中的不同对象.
- 测试期间测试阵列的大小会有所不同.
- 对于每个阵列大小/队列实现组合,运行100个测试并计算平均每次测试时间.
- 每个测试包括用所有对象填充每个队列,然后全部删除它们.
- 以毫秒为单位测量时间.
测试结果:
- 低于10,000个元素,LinkedList和ArrayDeque测试平均为1毫秒以下的水平.
- 随着数据集变大,ArrayDeque和LinkedList平均测试时间之间的差异变得更大.
- 在测试大小为9,900,000个元素时,LinkedList方法比ArrayDeque方法花费了大约165%的时间.
图形:
带走:
- 如果您的要求是存储100或200个元素,那么使用任何一个队列都不会产生太大的影响.
- 但是,如果您是在移动设备上进行开发,则可能需要使用
ArrayList或者ArrayDeque对可能需要列表的最大容量进行良好猜测,因为严格的内存限制. - 很多代码都存在,
LinkedList在决定使用ArrayDeque特别是因为它没有实现List接口时使用了这么谨慎的编写(我认为这个原因足够大).可能是你的代码库广泛地与List接口对话,很可能你决定加入ArrayDeque.将它用于内部实现可能是一个好主意......
- 这个基准测试如何捕获由链表垃圾引起的 GC 时间？ (2认同)