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

请教个 Java LinkedList 用法的问题

  •  
  •   xloger · 2023-10-04 21:29:11 +08:00 · 1942 次点击
    这是一个创建于 434 天前的主题,其中的信息可能已经有所发展或是发生改变。
    之前看到个帖子<https://www.zhihu.com/question/563680801/answer/2750393567>里面的观点基本都是 ArrayList 全方位优于 LinkedList 。
    我总结了一下大概这几点:
    1 、ArrayList 内存占用远优于 LinkedList 。
    2 、LinkedList 因为设计原因,随机插入需要遍历,速度并不快。
    3 、作者自己都不用。(盯着这点说我觉得挺没意思的,因为这不是求知的理由)

    但是我想到了我最近的一个 LinkedList 的应用场景:我需要将用户手机的全部图片、视频按时间倒序添加到一个 List 里。基于 Android 的 API 限制,图片和视频的查询是分开的,故有大量的中间插入需求。
    按照我的理解,ArrayList 这种场景下会有大量的数据后移操作,故我认为这时候用 LinkedList 要科学很多?

    疑问:
    1 、上述场景中,ArrayList 还是优于 LinkedList 么?如果是原因是什么?
    2 、是否有更合适的数据结构? Java 似乎是没有根据比较器在插入时根据内容决定插入位置的 List 。
    3 、在并发场景下,最合适的实现方案是什么?按我的理解是加个读写锁?用 CopyOnWriteArrayList 我感觉在这个场景下是一个性能很差的方案。
    4 、第三个问题中,实际上我是用 Kotlin 的协程实现的,用 mutex 锁的,有没有更优的方案?(比如直接创建单线程的协程?)

    国庆假期也不知道有没有人逛 V2......
    22 条回复    2024-01-24 11:57:59 +08:00
    geelaw
        1
    geelaw  
       2023-10-04 21:37:57 +08:00
    只有反复修改的情况下才需要考虑数组/链表等数据结构。

    >我需要将用户手机的全部图片、视频按时间倒序添加到一个 List 里。基于 Android 的 API 限制,图片和视频的查询是分开的,故有大量的中间插入需求。

    这个很简单,你可以先把所有的图片和视频都弄到一个巨大的 ArrayList 里,然后再排序。我没做过 Android 开发,猜测 API 提供按时间顺序分别获取图片、视频的功能,那么你可以先准备好两个 ArrayList ,分别得到正确顺序的图片、视频,然后做一轮归并即可。
    Ericcccccccc
        2
    Ericcccccccc  
       2023-10-04 22:01:38 +08:00
    就说一点吧, 这玩意的作者都说他从来没用过 LinkedList, 也没见别人用过.
    kingbill
        3
    kingbill  
       2023-10-04 22:06:00 +08:00
    LinkedList 有顺序,别的场景没用过
    hairoy
        4
    hairoy  
       2023-10-04 22:11:52 +08:00
    2&3. 我的想法是,单线程 TreeMap ,多线程 ConcurrentSkipListMap ,时间戳可以放在 key 或 value 里,使用自定义排序器
    Leviathann
        5
    Leviathann  
       2023-10-04 22:46:27 +08:00
    需要插入到排序的某个位置? treemap 咯

    不然怎么利用顺序信息?
    9c04C5dO01Sw5DNL
        6
    9c04C5dO01Sw5DNL  
       2023-10-04 23:03:46 +08:00
    因为很少有场景只是 append 、遍历,而没有随机插入、访问
    9c04C5dO01Sw5DNL
        7
    9c04C5dO01Sw5DNL  
       2023-10-04 23:06:37 +08:00
    @giiiiiithub 修正:因为很少有场景只是增删改 、遍历,而没有随机访问
    xiaofan305
        8
    xiaofan305  
       2023-10-04 23:21:47 +08:00 via Android
    @giiiiiithub 现在做着的项目就有这种。我是用 LinkedList
    xloger
        9
    xloger  
    OP
       2023-10-05 10:27:26 +08:00
    @geelaw 嗯,你这种是一种很科学的方式。我最开始为啥没用这种是我考虑到我的实际需求还有一部分是:每获取到一部分图片、视频就要展示给用户看(因此有并发场景),那这个巨大的 ArrayList 是需要多次排序的有浪费。
    但我刚刚突然想到了,这其实是每次排序了一部分,剩下的数据也是增量排序(把新数据放末尾就不会 UI 显示不对),实际上是没多少浪费的计算的。

    然后我提问的困惑之一是:假如我在这种情况下硬要 ArrayList 、LinkedList 里二选一,ArrayList 在存在后移操作的情况下性能还是更好么?
    然后我思考了一下您的想法,这样理解对不对:在有大量中间插入需求的时候,ArrayList 、LinkedList 的性能其实都很差。所以我们更应该做的是通过其他的方式(比如先插入再统一排序、或者 TreeMap 之类的方式)来规避这个问题,而不是强行比哪个差的方案更好一点。
    xloger
        10
    xloger  
    OP
       2023-10-05 10:33:34 +08:00
    @hairoy
    @Leviathann
    谢谢回复,一开始我确实是苦恼于 List 怎么没有 TreeMap 这样的根据比较器插入的数据结构。然后网上搜索一下之后无果后放弃了这个方向。
    但是现在一想,我实际上还是应该把 TreeMap 来当 List 用,因为这可能是最理想的方式(在插入时确定好顺序,且 Map 有良好的索引规避了 ArrayList 的后移、LinkedList 的查询)。
    虽然它可能会带来一些额外的小问题(比如时间戳一致的资源会不会导致覆盖),但这种我自己想办法规避一下就行。
    SoloCompany
        11
    SoloCompany  
       2023-10-05 15:34:19 +08:00
    除了 ArrayList 以外还有 ArrayDeque, LinkedList 应该是 never use
    ohwind
        12
    ohwind  
       2023-10-06 13:46:55 +08:00
    @Ericcccccccc 为什么不看完别人的贴子就急于发表自己的拙见?
    Ericcccccccc
        13
    Ericcccccccc  
       2023-10-06 13:56:32 +08:00
    @ohwind java 的作者表示自己从来没用过 linkedlist 是他自己说的.
    sl450282169
        14
    sl450282169  
       2023-10-08 10:26:43 +08:00   ❤️ 1
    @xloger #9 ArrayList 在中间随机插入数据时,只有扩容和移动元素位置之后的那部分元素的操作比较重,由于数组每次扩容 1.5 倍,在数组越大的情况下,扩容次数反而越少,因此在后续操作中,可以理想的看待为之需要插入元素(o(1))并移动元素位置后的那些元素(n-i)个.而 LinkedList 在中间插入元素时,需要持有当前数组的迭代器,然后遍历到指定位置(o(n)),因此数组越大,linkedlist 的插入耗时越多.
    sl450282169
        15
    sl450282169  
       2023-10-08 10:29:03 +08:00   ❤️ 1
    以目前的 java 来讲,仅有从头插入,linkedlist 速度比 arraylist 理想,但是在这种情况下,更推荐使用 Deque 拥有更优秀的方法设计.其他场景无脑选 arraylist
    sl450282169
        16
    sl450282169  
       2023-10-08 10:33:46 +08:00
    @xloger #9 单纯从此场景来看,你可以试试使用 ConcurrentSkipListSet,可以使插入的元素有序
    Aresxue
        17
    Aresxue  
       2023-10-08 11:09:03 +08:00
    @sl450282169 正解
    ohwind
        18
    ohwind  
       2023-11-20 17:01:00 +08:00
    @Ericcccccccc 所以你看完 OP 的帖子了吗
    Ericcccccccc
        19
    Ericcccccccc  
       2023-11-20 17:24:44 +08:00
    @ohwind 看了啊, 没有必要用 linkedlist
    ohwind
        20
    ohwind  
       2023-11-20 17:29:54 +08:00
    @Ericcccccccc 我的意思是,OP 已经提到了作者自己都不用,并且不认为这一点值得讨论。所以他是知道这一点的,而您的评论的只是在重复他说过的话
    Ericcccccccc
        21
    Ericcccccccc  
       2023-11-20 17:34:35 +08:00
    @ohwind 如果认真要讨论. 几万个数据没必要用 linkedlist.
    txzh007
        22
    txzh007  
       322 天前
    写撤销和回退撤销的时候用过链表,不过这种场景比较少. 需要高频次对数组长度进行修改还是 linkedlist,当然现在可以预先申请很大容量的 arraylist.
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5390 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 03:05 · PVG 11:05 · LAX 19:05 · JFK 22:05
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.