Java 中 ArrayList 和 LinkedList 查找指定元素，哪个效率高？

[rockss]

[Vamposine]

这不是基础么，指定位置必须是 arraylist 效率高

[feiyuanqiu]

contains ？复杂度是一样的。它们的差异在 java.util.List#get 和 java.util.List#add(int, E)

[insomnia1232]

遍历查找的话 没啥区别

[V2exUser]

查找的话，底层是数组的效率高，因为内存区是连续的。

[exonuclease]

都是 O(n)吧 如果不是排好序的

[jmc891205]

无序的话是同样的时间复杂度
有序的话是 ArrayList 好

[kiddult]

不管什么情况都是 ArrayList，ArrayList 占内存连续便宜，CPU 缓存比较吃香

[mrsatangel]

ArrayList 的 cache locality 更好

[rockss]

补充一下，是查找指定的元素（不是通过下标）

所以看起来 ArrayList 还是有一定的优势的（不过在时间复杂度分析上，应该没多大区别了）

[zhix]

因为 Cache Line 的存在，所以严格来说 ArrayList 的遍历速度更快一些。