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

Why does linked list delete and insert operation have complexity of O(1) ? shouldn't it be of O(n)

提问by Aditya Agarwal

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

据说LinkedList的remove和add操作的复杂度是O(1)。在的情况下，ArrayList它是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).

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

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

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

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

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 ?

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

回答by dasblinkenlight

Remove and the add operations are said to be of O(1) in case of LinkedListas, in LinkedListthe shift is not involved, but there is traverse operation involved right?

在LinkedListas的情况下，remove和add操作据说是O(1) ，在LinkedListshift中不涉及，但有遍历操作，对吗？

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 addand addFirst/addLastmethods.

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

Same goes for parameterless removeand removeFirst/removeLastmethods - they operate on list ends.

无参数remove和removeFirst/removeLast方法也是如此——它们在列表端操作。

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

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

回答by Rafael Lima

The complexity of removing is considered that you already have the pointer to the right position of the element you want to remove...

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

Is not considered the cost you took for finding it

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

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.

回答by Ankit Joshi

Yes, you are corrrect if you consider two operations (indexing and inserting) in one go. It is not true in this case because when you are inserting a node in the middle of a linked list, the assumption taken is that you are already at the address where you have to insert the node.

是的，如果您一次考虑两个操作（索引和插入），您是正确的。在这种情况下并非如此，因为当您在链表中间插入一个节点时，所采取的假设是您已经位于必须插入该节点的地址处。

The time complexity of accessing the node is O(n) whereas only inserting a node is O(1).

访问节点的时间复杂度为 O(n) 而仅插入节点的时间复杂度为 O(1)。

Insertion at the head requires you to add the element and update the head pointer.

在头部插入需要您添加元素并更新头部指针。

newnode->next = head;
head = newnode;

Insertion at the tail requires you to keep a pointer to the tail element, add the element at the tail and update the tail pointer.

在尾部插入需要你保留一个指向尾部元素的指针，在尾部添加元素并更新尾部指针。

tail->next = newnode;
tail = newnode;

Deleting the head element requires updating the head and deleting the previously head element.

删除 head 元素需要更新 head 并删除之前的 head 元素。

temp = head;
head = head->next;
delete temp; /* or free(temp); */

All the above are trivial operations and don't depend upon the number of elements in linked list. Hence, they are O(1)

以上都是微不足道的操作，不依赖于链表中元素的数量。因此，它们是 O(1)

Deleting the tail element would, however, be a O(n) operation because even though you might have a tail pointer, you would still need the penultimate node that would be setup as the new tail node ( by updating the tail pointer and setting the node's next member to NULL). For this, you need to traverse through the whole linked list.

然而，删除尾元素将是一个 O(n) 操作，因为即使您可能有尾指针，您仍然需要将设置为新尾节点的倒数第二个节点（通过更新尾指针并设置节点的下一个成员为 NULL）。为此，您需要遍历整个链表。

penultimate_el = find_penultimate_el(head); /* this is O(n) operation */
delete tail; /* or free(tail) */
tail = penultimate_el;
tail->next = NULL;

回答by Raman Sahasi

ArrayList provides resizable-array and stores "references" or "pointers" to actual storage. This array of references has to be recreated if the array is expanded beyond its allocated size. In other words, inserting a node at the beginning would require either all the existing elements to be moved up one, or to re-allocate the whole list if it's beyond it's allocated size. That's why insertion is O(n).

ArrayList 提供可调整大小的数组并将“引用”或“指针”存储到实际存储。如果数组扩展到超出其分配的大小，则必须重新创建此引用数组。换句话说，在开头插入一个节点将需要将所有现有元素向上移动一个，或者如果整个列表超出分配的大小，则需要重新分配整个列表。这就是为什么插入是O(n).

A LinkedList consists of a chain of nodes; each node is separated allocated. And so while inserting, it's not necessary to traverse all the nodes. And that's why it has the complexity O(1). However, if you're inserting at end and you have reference of only first node, then you may have to traverse the entire list and thus complexity in this case will be O(n).

LinkedList 由一系列节点组成；每个节点是分开分配的。所以在插入时，没有必要遍历所有节点。这就是为什么它具有复杂性O(1)。 但是，如果您在最后插入并且您只有第一个节点的引用，那么您可能必须遍历整个列表，因此在这种情况下的复杂性将为 O(n)。

EDIT

编辑

If you look at the source code of java.util.LinkedListyou can find that LinkedListalways keeps the track of last element

如果您查看源代码，java.util.LinkedList您会发现LinkedList始终跟踪最后一个元素

Following are some code snippets from actual java.util.LinkedListclass.

以下是来自实际java.util.LinkedList课程的一些代码片段。

package java.util;

...

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     */
    transient Node<E> last;


    ...
    ...


    /**
     * Appends the specified element to the end of this list.
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }



    ...
    ...


    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }


    ...
    ...

}

See particularly the linkLast()method. It doesn't traverse the entire list. It just inserts the element at the end of the list and that's why time complexity is O(1).

具体见linkLast()方法。它不会遍历整个列表。它只是在列表的末尾插入元素，这就是时间复杂度为 的原因O(1)。

回答by Kunal Hazard

In array if we see the implementation from C language point of view then it will give us a clear understanding. While we can add and remove elements at constant time in array i.e we don't need to traverse through the entire array Eg: If the array is [1,2,3,4] the 5 can be added directly at Arr[arr.length] postion , similarly we can remove element at constant time ,position to be deleted is Arr[arr.length-1], but let us see a scenario when the array size you have declared is 4 and we want add one more elements then we can clearly see that there is no space for the elements to be added, therefore what we need to do is to make a new array of size lets say double of previous array i.e size 8 , then all the elements of previous array has to be copied here and the new elements is added at 5th position i.e Arr[arr.length] , therefore the insertion time complexity is O(n) as it is directly proportional to number of elements that previous array has.

在数组中，如果我们从 C 语言的角度来看实现，那么它会让我们有一个清晰的理解。虽然我们可以在数组中以恒定时间添加和删除元素，即我们不需要遍历整个数组 例如：如果数组是 [1,2,3,4]，则 5 可以直接添加到 Arr[arr。 length] 位置，同样我们可以在固定时间删除元素，要删除的位置是Arr[arr.length-1]，但是让我们看看你声明的数组大小是4，然后我们想再添加一个元素的场景我们可以清楚地看到没有空间可以添加元素，因此我们需要做的是创建一个大小为前一个数组的两倍的新数组，即大小为 8 ，那么前一个数组的所有元素都必须是复制到此处并在第 5 个位置添加新元素，即 Arr[arr.length] ，

Now coming to linked list it doesn't have fixed size(it is dynamically allocated at heap memory) declared we can track the first and last position by head and tails pointer therefore irrespective of linkedlist size we need to just change the pointer of head and tail, making time complexity to O(1) ,for adding at last make a new node, change the link part of current tail to this new node address and make this new node as tail.For inserting at first we need to make new node , set the link part of this node as current head address and atlast make this new node as head thus adding a element at 1st position just by altering the one node therefore time complexity will be O(1).

现在来到链表，它没有固定大小（它在堆内存中动态分配）声明我们可以通过头和尾指针跟踪第一个和最后一个位置，因此无论链表大小如何，我们只需要更改头和尾，时间复杂度为 O(1) ，最后添加创建一个新节点，将当前尾的链接部分更改为这个新节点地址，并将这个新节点作为尾。 对于首先插入我们需要创建新节点, 将此节点的链接部分设置为当前头地址，并最终将此新节点设为头，从而仅通过更改一个节点就在第一个位置添加一个元素，因此时间复杂度为 O(1)。