V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
rockss
V2EX  ›  程序员

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

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

    所以看起来 ArrayList 还是有一定的优势的(不过在时间复杂度分析上,应该没多大区别了)
    zhix
        10
    zhix  
       2018-12-27 16:04:23 +08:00
    因为 Cache Line 的存在,所以严格来说 ArrayList 的遍历速度更快一些。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2731 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 09:51 · PVG 17:51 · LAX 01:51 · JFK 04:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.