问题描述
我精通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补充物去除的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！