java - 哪种列表实现最适合从前面和后面删除和插入？

Question

我正在研究一种算法，该算法将一小部分对象存储为较大对象集的子列表。对象本质上是有序的，因此需要一个有序列表。

最常执行的操作将按频率顺序排列:

1. 从列表中检索第 n 个元素(对于任意 n)
2. 在列表的开头或结尾插入一个
3. 从列表中删除第一个或最后一个元素(对于某些 任意 n)

永远不会从中间删除和插入，因此无需考虑效率。

我的问题是，对于 Java 中的这个用例，List 的哪种实现最有效(即 LinkedList、ArrayList、Vector 等)？请通过解释不同数据结构的实现来捍卫您的答案，以便我做出明智的决定。

谢谢。

注意

不，这不是作业问题。不，我没有可以为我做这项工作的军队研究助理。

Answer 1

根据您的第一个标准(任意访问)，您应该使用 ArrayList。 ArrayLists(和一般的数组)提供恒定时间的查找/检索。相反，在 LinkedList 中查找项目需要线性时间。

对于ArrayLists，末尾的插入或删除是自由的。它也可能与 LinkedLists 一起使用，但那将是特定于实现的优化(否则它是线性的)。

对于 ArrayLists，前面的插入或删除需要线性时间(随着空间的一致重用，这些可能会根据实现而变得不变)。列表前面的 LinkedList 操作是常量。

最后两个用例在某种程度上相互平衡，但最常见的用例肯定建议使用基于数组的存储。

至于基本的实现细节: ArrayLists 基本上只是内存的顺序部分。如果你知道起点在哪里，你可以只做一次加法来找到任何元素的位置。前端的操作成本很高，因为可能必须移动元素以腾出空间。

链表在内存中是不相交的，由相互链接的节点组成(引用第一个节点)。要找到第 n 个节点，您必须从第一个节点开始并跟随链接，直到到达所需的节点。前面的操作只需要创建一个节点并更新您的起始指针。