为什么链表删除和插入操作的复杂度为 O(1) ?不应该是 O(n) [英] Why does linked list delete and insert operation have complexity of O(1) ? shouldn't it be of O(n)

问题描述

据说LinkedList的remove和add操作的复杂度是O(1).在 ArrayList 的情况下，它是 O(n).

It is said that the complexity of the LinkedList remove and the add operation is of O(1). and in case of ArrayList it is of O(n).

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

Calculation for ArrayList of size "M" : if i want to remove the element at Nth position then i can directly go to the Nth position using index in one go (i don't have to traverse till Nth index) and then i can remove the element, till this point the complexity is O(1) then i will have to shift the rest of the elements(M-N shifts) so my complexity will be linear i.e. O(M-N+1). and hence deletion or insertion at the last will give me the best performence( as N ~ M) and deletion or insertion at the start will be worst (as N ~ 1).

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

Now the LisnkedList of size "M" : as we can not directly reach the Nth element in the LinkedList, to access the Nth element we have to traverse N elements, so the search in the LinkedList is costlier then the ArrayList...but 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 rigth ? so the complexity should be of order O(n) where Worst performence will be at the tail node and best performence will be at the head node.

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

Could anyone please explain me why don't we consider the traverse cost while calculating the complexity of LinkedList remove operation ?

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

So i wants to understand how it works in java.util package. and if i want to implemet the same in C or C++ how would i achieve the O(1) for random deletion and insertion in LinkedList ?

推荐答案

删除和添加操作在LinkedList的情况下被称为O(1)，因为在LinkedList中不涉及移位，但有遍历操作涉及对吗?

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 为其 <所做的事情代码>添加和addFirst/addLast 方法.

Adding to either end of a linked list does not require a traversal, as long as you keep a reference to both ends of the list. This is what Java does for its add and addFirst/addLast methods.

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

Same goes for parameterless remove and removeFirst/removeLast methods - they operate on list ends.

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

remove(int) and remove(Object) operations, on the other hand, are not O(1). They requires traversal, so you correctly identified their costs as O(n).

这篇关于为什么链表删除和插入操作的复杂度为 O(1) ?不应该是 O(n)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！