首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >ArrayList与LinkedList的JDK8性能比较

问ArrayList与LinkedList的JDK8性能比较
EN

Stack Overflow用户
提问于 2016-08-12 23:59:32
回答 3查看 89关注 0票数 1

我开始看到越来越多的基准测试表明,在“大型”插入的性能方面,ArrayList压垮了LinkedList。示例如下:Gluelist

代码语言:javascript
复制
Adding(1M) Elements (5 Tests Avg.)

LinkedList: 174.8 milliseconds
ArrayList:  76.4 milliseconds
GlueList:   39.2 milliseconds

Adding(10M) Elements (5 Tests Avg.)

LinkedList: 8975.6 milliseconds
ArrayList:  4118.2 milliseconds
GlueList:   3320.1 milliseconds

我在RHEL 7.2上用JDK8.latest运行了类似的测试,看到了类似的结果。我的印象是,即使在最坏的情况下,LinkedList插入也是O(1),并且由于复制操作,ArrayList占用> O(1) (我意识到我们可以讨论摊销成本,但这超出了范围)。我的问题是:在容量接近极限时,如果ArrayList强制执行拷贝操作,LinkedList的性能如何比ArrayList差?

EN

回答 3

Stack Overflow用户

发布于 2016-08-14 07:56:55

它们有相同的大O,但这并不能告诉你关于恒定关系的信息。它告诉你它们在理想化的机器上的行为,而不是真正的机器。

LinkedList分配和使用更多的内存。它为每个节点创建一个24字节的对象,而作为ArrayList,每个引用使用4个字节(通常),并且创建的对象要少得多。

票数 1
EN

Stack Overflow用户

发布于 2016-08-13 00:05:42

大O在这一点上对你没有真正的帮助。它告诉你增长的方向,但它不会给你绝对的数字。

ArrayList使用数组,并对本机System.arrayCopy()调用进行了高度优化。

LinkedLists必须为每个单独的节点创建一个包装器对象,并在其中存储指向下一个和前一个节点的指针。这需要时间。

ArrayList在插入时不会创建单个对象,除非它调整数组的大小,而这种情况并不经常发生。

票数 0
EN

Stack Overflow用户

发布于 2016-08-13 00:17:30

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/38922137

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档