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屋！