ArrayList 与 LinkedList 的随机访问和链表添加删除 [英] ArrayList vs LinkedList for both Random-Access & Additions-Removals
问题描述
我非常了解 ArrayList 和 LinkedList 的优缺点.ArrayList 适用于随机访问,当添加和删除较少时,反之亦然.如果我需要一个既需要进行随机访问又需要添加 & 的数据结构,该怎么办?经常从列表中删除项目?
I am well versed with pros and cons of ArrayList and LinkedList. ArrayList is preferred for random access, when additions and removals are less, and vice versa. What if I need a data structure where I need to do both random access, and need to add & remove items from the list often?
选择哪一个?
推荐答案
这些数据结构与 API 兼容,只需对您的代码进行基准测试/分析即可.
These data structures are API-compatible, just benchmark/profile your code with both.
另一个提示:使用 ArrayList
假设您执行 N
查找和 N
突变.这总计为 O(N) + O(N * N) <=>O(N^2)
复杂度.使用 LinkedList
你会得到 O(N*N) + O(N) <=>O(N^2)
(线性查找次数 N
+ 恒定时间变异次数 N
).所以这两种数据结构都具有可比性.
Another hint: with ArrayList
assume you perform N
lookups and N
mutations. This totals to O(N) + O(N * N) <=> O(N^2)
complexity. With LinkedList
you'll get O(N*N) + O(N) <=> O(N^2)
(linear lookup times N
+ constant time mutation times N
). So both data structures are comparable.
如果你愿意更深入一点,scala.collection.immutable.Vector
有 查找和插入/删除的摊销固定成本.它是不可变的,因此是线程安全的!它是通过一些复杂的数据结构实现的.
If you are willing to go a little bit deeper into the rabbit hole, scala.collection.immutable.Vector
has amortized constant cost of both lookup and insertions/removal. And it's immutable, thus thread-safe! It's achieved using some sophisticated data structures underneath.
这篇关于ArrayList 与 LinkedList 的随机访问和链表添加删除的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!