为什么链表删除和插入操作的复杂度为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的情况下,add操作被认为是O(1),因为在LinkedList中不涉及Shift,但是有涉及rigth的遍历操作？所以复杂度应该是O(n)的顺序,其中最差性能将在尾节点处,并且最佳性能将在头节点处.

任何人都可以解释一下为什么我们在计算LinkedList删除操作的复杂性时不考虑遍历成本？

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

Answer 1

删除和添加操作被认为是O(1)在LinkedListas的情况下,在LinkedList移位中没有涉及,但是涉及遍历操作吗？

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

无参数remove和removeFirst/ removeLast方法也是如此 - 它们在列表末端运行.

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

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.