java - 为什么链表删除和插入操作的复杂度为 O(1)？不应该是 O(n)

Question

据说LinkedList删除和添加操作的复杂度是O(1)。在 ArrayList 的情况下，它是 O(n)。

大小为“M”的 ArrayList 的计算:如果我想删除第 N 个位置的元素，那么我可以直接使用索引一次性转到第 N 个位置(我不必遍历到第 N 个索引)然后我可以删除元素，直到此时复杂度为 O(1) 然后我将不得不移动其余元素(M-N 移动)所以我的复杂度将是线性的，即 O(M-N+1)。因此在最后删除或插入会给我最好的性能(如 N ~ M)，而在开始时删除或插入将是最差的(如 N ~ 1)。

现在是大小为“M”的 LisnkedList:因为我们不能直接到达 LinkedList 中的第 N 个元素，要访问第 N 个元素我们必须遍历 N 个元素，所以在 LinkedList 中的搜索比 ArrayList 中的搜索成本更高。 .but Remove 和 add 操作在 LinkedList 的情况下据说是 O(1) 的，因为在 LinkedList 中不涉及 Shift，但是涉及遍历操作吗？所以复杂度应该是 O(n) 阶，其中最差性能将出现在尾节点，而最佳性能将出现在头节点。

谁能解释一下为什么我们在计算 LinkedList 删除操作的复杂度时不考虑遍历成本？

所以我想了解它在 java.util 包中的工作原理。如果我想在 C 或 C++ 中实现相同的功能，我将如何在 LinkedList 中实现随机删除和插入的 O(1)？

Answer 1

Remove and the add operations are said to be of O(1) in case of LinkedList as, in LinkedList the shift is not involved, but there is traverse operation involved right?

添加到链表的任一端不需要遍历，只要您保留对链表两端的引用即可。这就是 Java 为其 add 所做的和 addFirst/addLast方法。

同样适用于无参数 remove和 removeFirst/removeLast方法 - 它们对列表末端进行操作。

remove(int)和 remove(Object)另一方面，操作不是 O(1)。它们需要遍历，因此您正确地将它们的成本确定为 O(n)。