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

time-complexity data-structures collections java linked-list

2022-09-01 21:44:44

据说LinkedList删除和添加操作的复杂性是。如果是.cO(1)ArrayListO(n)

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

现在，大小为“M”的LisnkedList：由于我们无法直接到达LinkedList中的第N个元素，因此要访问第N个元素，我们必须遍历N个元素，因此LinkedList中的搜索成本高于ArrayList...但是在LinkedList的情况下，删除和添加操作被称为O（1），因为在LinkedList中不涉及Shift，但是涉及遍历操作？因此，复杂性应为 O（n）阶，其中最差性能位于尾节点，最佳性能位于头节点。

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

所以我想了解它在java.util包中是如何工作的。如果我想在C或C++我如何实现O（1）在LinkedList中随机删除和插入？

答案 1

删除和添加操作被称为O（1）在as的情况下，在移位不涉及，但有遍历操作涉及对吗？LinkedListLinkedList

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

无参数删除和删除第一/删除最后方法也是如此 - 它们在列表末端操作。

另一方面，remove（int） 和 remove（Object） 操作不是 O（1）。它们需要遍历，因此您可以正确地将其成本标识为 O（n）。

答案 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.