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

Question

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

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

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

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

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

原文由 Aditya Agarwal 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 LinkedList 的情况下，删除和添加操作据说是 O(1)，因为在 LinkedList 不涉及移位，但涉及遍历操作，对吗？

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

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

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

原文由 Sergey Kalinichenko 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

删除的复杂性被认为是您已经拥有指向要删除的元素的正确位置的指针……

不考虑您为找到它而花费的成本

Information on this topic is now available on Wikipedia at: Search data structure

    +----------------------+----------+------------+----------+--------------+
    |                      |  Insert  |   Delete   |  Search  | Space Usage  |
    +----------------------+----------+------------+----------+--------------+
    | Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
    | Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
    | Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
    | Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
    | Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
    | Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
    | Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
    | Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
    +----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list (i.e. if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time.
** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.

原文由 Rafael Lima 发布，翻译遵循 CC BY-SA 3.0 许可协议