请教个 Java LinkedList 用法的问题

[xloger]

之前看到个帖子<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......

[geelaw]

只有反复修改的情况下才需要考虑数组/链表等数据结构。

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

这个很简单，你可以先把所有的图片和视频都弄到一个巨大的 ArrayList 里，然后再排序。我没做过 Android 开发，猜测 API 提供按时间顺序分别获取图片、视频的功能，那么你可以先准备好两个 ArrayList ，分别得到正确顺序的图片、视频，然后做一轮归并即可。

[Ericcccccccc]

就说一点吧, 这玩意的作者都说他从来没用过 LinkedList, 也没见别人用过.

[kingbill]

LinkedList 有顺序，别的场景没用过

[hairoy]

2&3. 我的想法是，单线程 TreeMap ，多线程 ConcurrentSkipListMap ，时间戳可以放在 key 或 value 里，使用自定义排序器

[Leviathann]

需要插入到排序的某个位置？ treemap 咯

不然怎么利用顺序信息？

[giiiiiithub]

因为很少有场景只是 append 、遍历，而没有随机插入、访问

[giiiiiithub]

@giiiiiithub 修正：因为很少有场景只是增删改 、遍历，而没有随机访问

[xiaofan305]

@giiiiiithub 现在做着的项目就有这种。我是用 LinkedList

[xloger]

@geelaw 嗯，你这种是一种很科学的方式。我最开始为啥没用这种是我考虑到我的实际需求还有一部分是：每获取到一部分图片、视频就要展示给用户看（因此有并发场景），那这个巨大的 ArrayList 是需要多次排序的有浪费。
但我刚刚突然想到了，这其实是每次排序了一部分，剩下的数据也是增量排序（把新数据放末尾就不会 UI 显示不对），实际上是没多少浪费的计算的。

然后我提问的困惑之一是：假如我在这种情况下硬要 ArrayList 、LinkedList 里二选一，ArrayList 在存在后移操作的情况下性能还是更好么？
然后我思考了一下您的想法，这样理解对不对：在有大量中间插入需求的时候，ArrayList 、LinkedList 的性能其实都很差。所以我们更应该做的是通过其他的方式（比如先插入再统一排序、或者 TreeMap 之类的方式）来规避这个问题，而不是强行比哪个差的方案更好一点。

[xloger]

@hairoy
@Leviathann
谢谢回复，一开始我确实是苦恼于 List 怎么没有 TreeMap 这样的根据比较器插入的数据结构。然后网上搜索一下之后无果后放弃了这个方向。
但是现在一想，我实际上还是应该把 TreeMap 来当 List 用，因为这可能是最理想的方式（在插入时确定好顺序，且 Map 有良好的索引规避了 ArrayList 的后移、LinkedList 的查询）。
虽然它可能会带来一些额外的小问题（比如时间戳一致的资源会不会导致覆盖），但这种我自己想办法规避一下就行。

[SoloCompany]

除了 ArrayList 以外还有 ArrayDeque, LinkedList 应该是 never use

[ohwind]

@Ericcccccccc 为什么不看完别人的贴子就急于发表自己的拙见？

[Ericcccccccc]

@ohwind java 的作者表示自己从来没用过 linkedlist 是他自己说的.

[sl450282169]

@xloger #9 ArrayList 在中间随机插入数据时,只有扩容和移动元素位置之后的那部分元素的操作比较重,由于数组每次扩容 1.5 倍,在数组越大的情况下,扩容次数反而越少,因此在后续操作中,可以理想的看待为之需要插入元素(o(1))并移动元素位置后的那些元素(n-i)个.而 LinkedList 在中间插入元素时,需要持有当前数组的迭代器,然后遍历到指定位置(o(n)),因此数组越大,linkedlist 的插入耗时越多.

[sl450282169]

以目前的 java 来讲,仅有从头插入,linkedlist 速度比 arraylist 理想,但是在这种情况下,更推荐使用 Deque 拥有更优秀的方法设计.其他场景无脑选 arraylist

[sl450282169]

@xloger #9 单纯从此场景来看,你可以试试使用 ConcurrentSkipListSet,可以使插入的元素有序

[Aresxue]

@sl450282169 正解

[ohwind]

@Ericcccccccc 所以你看完 OP 的帖子了吗

[Ericcccccccc]

@ohwind 看了啊, 没有必要用 linkedlist

[ohwind]

@Ericcccccccc 我的意思是，OP 已经提到了作者自己都不用，并且不认为这一点值得讨论。所以他是知道这一点的，而您的评论的只是在重复他说过的话

[Ericcccccccc]

@ohwind 如果认真要讨论. 几万个数据没必要用 linkedlist.

[txzh007]

写撤销和回退撤销的时候用过链表,不过这种场景比较少. 需要高频次对数组长度进行修改还是 linkedlist,当然现在可以预先申请很大容量的 arraylist.