这是一个创建于 414 天前的主题，其中的信息可能已经有所发展或是发生改变。
之前看到个帖子<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......
我总结了一下大概这几点：
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
 |
1
geelaw 2023-10-04 21:37:57 +08:00
只有反复修改的情况下才需要考虑数组/链表等数据结构。
>我需要将用户手机的全部图片、视频按时间倒序添加到一个 List 里。基于 Android 的 API 限制，图片和视频的查询是分开的，故有大量的中间插入需求。 这个很简单，你可以先把所有的图片和视频都弄到一个巨大的 ArrayList 里，然后再排序。我没做过 Android 开发，猜测 API 提供按时间顺序分别获取图片、视频的功能，那么你可以先准备好两个 ArrayList ，分别得到正确顺序的图片、视频，然后做一轮归并即可。 |
 |
2
Ericcccccccc 2023-10-04 22:01:38 +08:00
就说一点吧, 这玩意的作者都说他从来没用过 LinkedList, 也没见别人用过.
|
 |
3
kingbill 2023-10-04 22:06:00 +08:00
LinkedList 有顺序，别的场景没用过
|
 |
4
hairoy 2023-10-04 22:11:52 +08:00
2&3. 我的想法是，单线程 TreeMap ，多线程 ConcurrentSkipListMap ，时间戳可以放在 key 或 value 里，使用自定义排序器
|
 |
5
Leviathann 2023-10-04 22:46:27 +08:00
需要插入到排序的某个位置？ treemap 咯
不然怎么利用顺序信息？ |
 |
6
9c04C5dO01Sw5DNL 2023-10-04 23:03:46 +08:00
因为很少有场景只是 append 、遍历，而没有随机插入、访问
|
|
7
9c04C5dO01Sw5DNL 2023-10-04 23:06:37 +08:00
@giiiiiithub 修正：因为很少有场景只是增删改 、遍历，而没有随机访问
|
 |
8
xiaofan305 2023-10-04 23:21:47 +08:00 via Android
@giiiiiithub 现在做着的项目就有这种。我是用 LinkedList
|
 |
9
xloger OP @geelaw 嗯，你这种是一种很科学的方式。我最开始为啥没用这种是我考虑到我的实际需求还有一部分是：每获取到一部分图片、视频就要展示给用户看（因此有并发场景），那这个巨大的 ArrayList 是需要多次排序的有浪费。
但我刚刚突然想到了，这其实是每次排序了一部分，剩下的数据也是增量排序（把新数据放末尾就不会 UI 显示不对），实际上是没多少浪费的计算的。 然后我提问的困惑之一是：假如我在这种情况下硬要 ArrayList 、LinkedList 里二选一，ArrayList 在存在后移操作的情况下性能还是更好么？ 然后我思考了一下您的想法，这样理解对不对：在有大量中间插入需求的时候，ArrayList 、LinkedList 的性能其实都很差。所以我们更应该做的是通过其他的方式（比如先插入再统一排序、或者 TreeMap 之类的方式）来规避这个问题，而不是强行比哪个差的方案更好一点。 |
|
10
xloger OP @hairoy
@Leviathann 谢谢回复，一开始我确实是苦恼于 List 怎么没有 TreeMap 这样的根据比较器插入的数据结构。然后网上搜索一下之后无果后放弃了这个方向。 但是现在一想，我实际上还是应该把 TreeMap 来当 List 用，因为这可能是最理想的方式（在插入时确定好顺序，且 Map 有良好的索引规避了 ArrayList 的后移、LinkedList 的查询）。 虽然它可能会带来一些额外的小问题（比如时间戳一致的资源会不会导致覆盖），但这种我自己想办法规避一下就行。 |
 |
11
SoloCompany 2023-10-05 15:34:19 +08:00
除了 ArrayList 以外还有 ArrayDeque, LinkedList 应该是 never use
|
 |
12
ohwind 2023-10-06 13:46:55 +08:00
@Ericcccccccc 为什么不看完别人的贴子就急于发表自己的拙见？
|
|
13
Ericcccccccc 2023-10-06 13:56:32 +08:00
@ohwind java 的作者表示自己从来没用过 linkedlist 是他自己说的.
|
 |
14
sl450282169 2023-10-08 10:26:43 +08:00  1
@xloger #9 ArrayList 在中间随机插入数据时,只有扩容和移动元素位置之后的那部分元素的操作比较重,由于数组每次扩容 1.5 倍,在数组越大的情况下,扩容次数反而越少,因此在后续操作中,可以理想的看待为之需要插入元素(o(1))并移动元素位置后的那些元素(n-i)个.而 LinkedList 在中间插入元素时,需要持有当前数组的迭代器,然后遍历到指定位置(o(n)),因此数组越大,linkedlist 的插入耗时越多.
|
|
15
sl450282169 2023-10-08 10:29:03 +08:00 1
以目前的 java 来讲,仅有从头插入,linkedlist 速度比 arraylist 理想,但是在这种情况下,更推荐使用 Deque 拥有更优秀的方法设计.其他场景无脑选 arraylist
|
|
16
sl450282169 2023-10-08 10:33:46 +08:00
@xloger #9 单纯从此场景来看,你可以试试使用 ConcurrentSkipListSet,可以使插入的元素有序
|
 |
17
Aresxue 2023-10-08 11:09:03 +08:00
@sl450282169 正解
|
|
18
ohwind 2023-11-20 17:01:00 +08:00
@Ericcccccccc 所以你看完 OP 的帖子了吗
|
|
19
Ericcccccccc 2023-11-20 17:24:44 +08:00
@ohwind 看了啊, 没有必要用 linkedlist
|
|
20
ohwind 2023-11-20 17:29:54 +08:00
@Ericcccccccc 我的意思是，OP 已经提到了作者自己都不用，并且不认为这一点值得讨论。所以他是知道这一点的，而您的评论的只是在重复他说过的话
|
|
21
Ericcccccccc 2023-11-20 17:34:35 +08:00
@ohwind 如果认真要讨论. 几万个数据没必要用 linkedlist.
|
 |
22
txzh007 302 天前
写撤销和回退撤销的时候用过链表,不过这种场景比较少. 需要高频次对数组长度进行修改还是 linkedlist,当然现在可以预先申请很大容量的 arraylist.
|
Select Language