我精通 ArrayList 和 LinkedList 的优缺点。ArrayList 是随机访问的首选，当添加和删除较少时，反之亦然。如果我需要一个既需要随机访问又需要经常从列表中添加和删除项目的数据结构怎么办？
选择哪一个？
问问题
2981 次
2 回答
3
这些数据结构与 API 兼容，只需使用两者对您的代码进行基准测试/分析即可。
另一个提示：ArrayList假设您执行N查找和N突变。这加起来很O(N) + O(N * N) <=> O(N^2)复杂。LinkedList你会得到（O(N*N) + O(N) <=> O(N^2)线性查找时间N+恒定时间突变时间N）。所以这两种数据结构是可比的。
如果您愿意更深入地研究兔子洞，scala.collection.immutable.Vector则已摊销了查找和插入/删除的固定成本。它是不可变的，因此是线程安全的！它是使用下面一些复杂的数据结构来实现的。
于 2012-10-20T07:44:08.403 回答
1
如果你想随机访问 ArrayList，你可以将它用作普通列表并添加/删除项目。
ArrayList 的内存是按块分配的，除非您的 ArrayList 变得巨大，否则它可能会耗尽内存。
由于您没有提到您是否有任何内存限制（唯一的限制是随机访问），我会说 ArrayList 应该满足您的所有需求。
于 2012-10-20T07:41:06.010 回答