为什么链表的删除和插入操作具有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的复杂性和添加操作为 O（1）。如果是 ArrayList ，则它是 O（n）。

大小为 M的ArrayList的计算：如果我想删除第N个位置的元素，那么我可以使用索引一次性直接转到第N个位置（i不必遍历直到第N个索引），然后我就可以删除元素，直到这一点的复杂度为O（1），然后我将不得不移动其余元素（MN移位），因此我的复杂度将是线性的，即O（M-N + 1）。因此，最后删除或插入将使我表现最佳（为N〜M），而最开始的删除或插入将是最糟糕的情况（为N〜1）。

<现在，大小为 M的LisnkedList：由于我们无法直接到达LinkedList中的第N个元素，要访问第N个元素，我们必须遍历N个元素，因此LinkedList中的搜索比ArrayList更昂贵。但是在LinkedList的情况下，Remove和add的操作被称为O（1），因为在LinkedList中不涉及Shift，但是遍历操作是否涉及rigth？因此，复杂度应为O（n），其中最差的性能将在尾节点，而最佳性能将在头节点。

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

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

解决方案

在 LinkedList 的情况下，删除和添加操作被称为O（1），如 LinkedList 不涉及平移，但是涉及遍历操作对吗？

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

无参数 删除 和 removeFirst / removeLast 方法-它们在列表末尾运行。

删除（int） 和 删除（对象） 操作不是O（1）。它们需要遍历，因此您可以正确地将其成本标识为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).

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).

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.

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

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 ?

解决方案

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?

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.

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

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屋！