Java 中 ArrayList 和 LinkedList 查找指定元素，哪个效率高？
rockss · 2018-12-26 20:50:52 +08:00 · 4642 次点击这是一个创建于 2184 天前的主题，其中的信息可能已经有所发展或是发生改变。
10 条回复 • 2018-12-27 16:04:23 +08:00
 |
1
Vamposine 2018-12-26 21:00:07 +08:00 via iPhone  1
这不是基础么，指定位置必须是 arraylist 效率高
|
 |
2
feiyuanqiu 2018-12-26 21:01:58 +08:00
contains ？复杂度是一样的。它们的差异在 java.util.List#get 和 java.util.List#add(int, E)
|
 |
3
insomnia1232 2018-12-26 21:04:05 +08:00
遍历查找的话 没啥区别
|
 |
4
V2exUser 2018-12-26 21:05:49 +08:00 via Android 1
查找的话，底层是数组的效率高，因为内存区是连续的。
|
 |
5
exonuclease 2018-12-26 21:29:08 +08:00
都是 O(n)吧 如果不是排好序的
|
 |
6
jmc891205 2018-12-26 21:32:11 +08:00
无序的话是同样的时间复杂度
有序的话是 ArrayList 好 |
 |
7
kiddult 2018-12-26 21:53:00 +08:00
不管什么情况都是 ArrayList，ArrayList 占内存连续便宜，CPU 缓存比较吃香
|
 |
8
mrsatangel 2018-12-26 21:57:54 +08:00
ArrayList 的 cache locality 更好
|
 |
9
rockss OP 补充一下，是查找指定的元素（不是通过下标）
所以看起来 ArrayList 还是有一定的优势的（不过在时间复杂度分析上，应该没多大区别了） |
 |
10
zhix 2018-12-27 16:04:23 +08:00
因为 Cache Line 的存在，所以严格来说 ArrayList 的遍历速度更快一些。
|
Select Language