ArrayList和LinkedList的O大区别

Question

我确实找到了一些与此相关的主题，但帖子中存在矛盾，所以我想确认谁是正确的。

这个主题是我发现的： 在 Java 中何时使用 LinkedList 而不是 ArrayList？

点赞最多的答案是：

“对于链表

• 获取的时间复杂度为 O(n)
• 加法是 O(1)
• 删除是 O(n)
• Iterator.remove 的复杂度是 O(1)

对于数组列表

• 获取时间复杂度为O(1)
• add 是 O(1) 摊销，但最坏情况是 O(n)，因为必须调整数组大小并复制
• 删除是 O(n)"

但是后来其他人在这里发布了一个链接，上面写着：
http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html

Algorithm     ArrayList   LinkedList
access front     O(1)         O(1)
access back      O(1)         O(1)
access middle    O(1)         O(N)
insert at front  O(N)         O(1)
insert at back   O(1)         O(1)
insert in middle O(N)         O(1)

Answer 1

问题中引用的两个来源之间没有矛盾。

首先关于 LinkedLists 的一些想法： 在链表中，我们需要在列表中移动指针来访问任何特定元素，以删除它、检查它或在其之前插入新元素。由于 java.util.LinkedList 实现包含对列表前面和后面的引用，因此我们可以立即访问列表的前面和后面，这解释了为什么涉及列表前面或后面的任何操作都是 O(1 ）。如果使用迭代器完成操作，则指针已经位于您需要的位置。因此，从中间删除一个元素需要 O(n) 时间，但如果迭代器已经花费 O(n) 次操作到达中间，那么

iter.remove()

可以在 O(1) 中执行。

现在考虑ArrayList： 在底层，ArrayList 将数据存储在原始数组中。因此，虽然我们可以在 O(1) 时间内访问任何元素，但添加或删除元素将需要将整个数组向下移动一个元素，这需要 O(n) 时间。如果我们添加或删除最后一个元素，则不需要任何移位，因此可以在 O(1) 内运行。

这意味着调用

list.add(newItem)

需要O(1)，但有时列表末尾没有空间，因此需要将整个列表复制到新内存中，然后ArrayList才能执行添加操作。然而，由于每次 ArrayList 调整自身大小时，它都会使之前的容量加倍，因此在添加 n 个元素时，此复制操作只会发生 log₂ n 次。所以我们仍然说 add 在 O(1) 时间内运行。如果您知道创建 ArrayList 时将添加多少元素，则可以为其指定初始容量，从而通过避免复制操作来提高性能。