哪个是最好的集合 ArrayList 或 LinkedList

Question

我必须实现一种算法，该算法始终将条目插入最后并从第一个位置删除条目。他们说“ArrayList 存储在内存中的连续空间中。这允许操作系统使用优化，例如“当访问内存中的一个字节时，很可能很快就会访问下一个字节”。因此，ArrayList 是总比 LinkedList 快”但一种情况：在列表开头插入/删除元素时（因为必须移动数组中的所有元素）。在 ArrayList 的情况下，在末尾或中间添加/删除、迭代、访问元素都更快。在我的算法中，总是删除第一个元素。所以，总是发生移位。在这种情况下，我不应该使用数组列表？？

Answer 1

这实际上取决于您希望对结构做些什么。

如果大多数时候您只是在最后添加并从开始删除，那么Deque 的任何实现都可以。所以ArrayDeque或LinkedList可能是你最好的候选人。

ArrayDeque由数组支持，因此可以通过具有O(1)复杂性的索引快速访问，但它的缺点是添加速度可能比LinkedList有时需要调整支持数组的大小要慢。

LinkedList只是一个链表，所以它一直在增长/缩小，O(1)但通过索引访问并不是因为找到nth条目是O(n).