哪个列表实现最适合从正面和背面移除和插入？(Which list implementation is optimal for removing and inserting from the front

哪个列表实现最适合从正面和背面移除和插入？(Which list implementation is optimal for removing and inserting from the front and back?)

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

执行的最常见操作将按频率顺序执行：

从列表中检索第n个元素（对于某些任意n） 将单个插入列表的开头或结尾 从列表中删除第一个或最后一个n个元素（对于某些任意n）

从中间移除和插入将永远不会完成，因此无需考虑其效率。

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

谢谢。

注意

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

I am working on an algorithm that will store a small list of objects as a sublist of a larger set of objects. the objects are inherently ordered, so an ordered list is required.

The most common operations performed will be, in order of frequency:

retrieving the nth element from the list (for some arbitrary n) inserting a single to the beginning or end of the list removing the first or last n elements from the list (for some arbitrary n)

removing and inserting from the middle will never be done so there is no need to consider the efficiency of that.

My question is what implementation of List is most efficient for this use case in Java (i.e. LinkedList, ArrayList, Vector, etc)? Please defend your answer by explaining the implementation s of the different data structures so that I can make an informed decision.

Thanks.

NOTE

No, this is not a homework question. No, I do not have an army research assistants who can do the work for me.

最满意答案

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

对于ArrayLists，最后插入或删除是免费的。 它也可能是LinkedLists，但这将是一个特定于实现的优化（否则它是线性的）。

对于ArrayLists，前面的插入或删除需要线性时间（一致地重用空间，这些可能会变得不变，具体取决于实现）。 列表前面的LinkedList操作是不变的。

最后两个用例在某种程度上相互平衡，但是最常见的情况肯定是基于阵列的存储。

至于基本的实现细节：ArrayLists基本上只是内存的连续部分。 如果你知道开头的位置，你可以只做一个添加来找到任何元素的位置。 前面的操作是昂贵的，因为可能必须移动元件以腾出空间。

LinkedLists在内存中是不相交的，由彼此链接的节点组成（引用第一个节点）。 要查找第n个节点，您必须从第一个节点开始并按照链接进行操作，直到到达所需节点。 前面的操作只需要创建一个节点并更新你的开始指针。

Based on your first criteria (arbitrary access) you should use an ArrayList. ArrayLists (and arrays in general) provide lookup/retrieval in constant time. In contrast, it takes linear time to look up items in a LinkedList.

For ArrayLists, insertion or deletion at the end is free. It may also be with LinkedLists, but that would be an implementation-specific optimization (it's linear otherwise).

For ArrayLists, insertion or deletion at front requires linear time (with consistent reuse of space, these may become constant depending on implementation). LinkedList operations at front of list are constant.

The last two usage cases somewhat balance each other out, however your most common case definitely suggests array-based storage.

As far as basic implementation details: ArrayLists are basically just sequential sections of memory. If you know where the beginning is, you can just do a single addition to find the location of any element. Operations at the front are expensive because elements may have to be shifted to make room.

LinkedLists are disjoint in memory and consist of nodes linked to each other (with a reference to the first node). To find the nth node, you have to start at the first node and follow links until you reach the desired node. Operations at the front just require creating a node and updating your start pointer.