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

Question

据说LinkedList的删除和插入操作的复杂度为O(1)，而ArrayList的复杂度为O(n)。

对于大小为"M"的ArrayList：如果我想要删除第N个元素，我可以直接使用索引来到达第N个位置（无需遍历到第N个索引），然后删除该元素，到这一步的复杂度为O(1)，然后我将不得不移动其余的元素（M-N次移动），因此我的复杂度将是线性的，即O(M-N+1)。因此，在最后删除或插入会给我最佳的性能（因为N ~ M），而在开头删除或插入将是最差的（因为N ~ 1）。

现在考虑大小为"M"的LinkedList：由于我们无法直接到达LinkedList中的第N个元素，因此要访问第N个元素，我们必须遍历N个元素，因此在LinkedList中的搜索比ArrayList更昂贵...但是据说在LinkedList中删除和添加操作的复杂度为O(1)，因为在LinkedList中没有涉及到元素移动，但是遍历操作本身是否涉及成本呢？因此，复杂度应该是O(n)的，其中最差的性能将在尾节点处，最佳性能将在头节点处。

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

因此，我想了解它在java.util包中是如何工作的。如果我想在C或C++中实现相同的操作，如何实现LinkedList的随机删除和插入的O(1)复杂度？

- Aditya Agarwal

---

可能是LinkedList的add(int，E)的O(1)复杂度是如何实现的？的重复问题。 - jdigital

O(1)是指在双向链表中找到要执行操作的位置并进行插入或删除。如果该位置既不是列表的头部也不是尾部，并且您没有以其他方式显式地指向它，则必须找到它，这一部分的时间复杂度为O(n)。 - Lew Bloch

Answer 1

在LinkedList中，如果要进行删除和添加操作，它们被认为是O(1)，因为LinkedList中不涉及移位操作，但需要进行遍历操作，对吗？

只要保持对链表两端的引用，向链表的任一端添加元素都不需要进行遍历。这就是Java add 和 addFirst/addLast 方法所做的事情。

同样适用于无参数的remove和removeFirst/removeLast方法 - 它们操作列表的末尾。

另一方面，remove(int)和remove(Object)操作不是O(1)。它们需要遍历，所以您正确地将它们的成本识别为O(n)。

- Sergey Kalinichenko

---

在双向链表中，每个节点都可以访问前一个和后一个节点，因此当调用删除操作时，该节点可以在O(1)时间内将前一个节点与其后一个节点连接起来。@dasblinkenlight - RagHaven

@AndroidDev93 在 remove(n) 中，时间复杂度为 O(n) 的不是删除操作，而是获取到节点 n 的过程。 - Sergey Kalinichenko

@dasblinkenlight 如果您已经可以访问需要删除的节点，为什么还需要花费O(n)的时间来获取该节点？有一种版本的remove函数可以将Node对象作为输入。当您拥有对象时，就不需要花费O(n)的时间来获取对象了。因此，remove函数将是O(1)。 - RagHaven

由于节点被私有化并且不向外部提供，因此您无法访问节点。如果LinkedList.add方法向您返回了一个节点，那么您可以使用该节点以O(1)的时间复杂度删除元素。但实际情况并非如此。LinkedList.remove方法接收对象而不是节点，并需要遍历列表以查找包含该对象的节点。 - Kirill Gamazkov

您可以使用ListIterator迭代LinkedList以在O(n)时间内到达所需元素，然后使用List Iterator的remove()方法在稍后的时间点删除该元素，因为ListIterator已经有了对所需节点的引用，所以删除操作的时间复杂度为O(1)。这种方法将两个操作分开，但仍需要先前的O(n)遍历。 - Zippy

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.

- Rafael Lima

Answer 3

是的，如果您考虑一次进行两个操作（索引和插入），那么您是正确的。但在这种情况下并不是这样，因为当您在链表中间插入一个节点时，假设您已经到达了要插入节点的地址。

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

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

newnode->next = head;
head = newnode;

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

tail->next = newnode;
tail = newnode;

删除头元素需要更新头部并删除先前的头元素。

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

上述所有操作都是微不足道的，并且不取决于链表中元素的数量。因此，它们的时间复杂度为O(1)

然而，删除尾部元素将是一个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;

- Ankit Joshi

Answer 4

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

LinkedList由一系列节点组成；每个节点都是单独分配的。因此，在插入时，不必遍历所有节点。这就是它的时间复杂度为O(1)的原因。然而，如果你在末尾插入并且只有第一个节点的引用，则可能需要遍历整个列表，因此在这种情况下的时间复杂度为O(n)。 编辑 如果您查看java.util.LinkedList的源代码，您会发现LinkedList始终跟踪最后一个元素

以下是实际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++;
    }


    ...
    ...

}

请注意linkLast()方法。它不会遍历整个列表，只是将元素插入到列表的末尾，因此时间复杂度为O(1)。

- Raman Sahasi

---

当我想要在链表中插入一个元素时，它是否已经知道要插入的节点的地址？链表是否在某个地方存储每个元素的地址？如果我错了，请纠正我，但我认为它只知道头节点的地址，并从头节点遍历到第N个元素？在这种情况下，在链表的第N个位置添加元素的复杂度将是“N”吗？ - Aditya Agarwal

@AdityaAgarwal，是的，你说得对。但事实上，java.util包中提供的 LinkedList 会跟踪最后一个元素。因此，在插入时，它不必遍历整个列表。请参见编辑后的答案。 - Raman Sahasi

这意味着在头部或尾部插入元素的时间复杂度为O(1)，但在中间第N个位置添加元素的复杂度将为O(N)，因为Java.util包具有头节点和尾节点的地址。 - Aditya Agarwal

谢谢您的回复。您有任何支持您上次回答的参考资料吗？感谢您的帮助。 - Aditya Agarwal

@AdityaAgarwal 请访问StackOverflow上的这个答案。为什么在链表中间插入是O(1)？ - Raman Sahasi

Answer 5

在数组中，如果我们从C语言的角度来看实现，那么它将给我们一个清晰的理解。虽然我们可以在数组中以常数时间添加和删除元素，即我们不需要遍历整个数组。例如：如果数组是[1,2,3,4]，则5可以直接添加到Arr[arr.length]位置，同样，我们可以在常数时间内删除元素，要删除的位置是Arr[arr.length-1]，但让我们看一个场景，当您声明的数组大小为4时，我们想添加一个以上的元素，那么我们可以清楚地看到没有空间添加元素，因此我们需要做的是制作一个新的数组，大小为先前数组的两倍，即大小为8，然后必须将所有先前数组的元素复制到此处，并在第5个位置添加新元素，即Arr[arr.length]，因此插入时间复杂度为O(n)，因为它与先前数组具有的元素数量成正比。

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

- Kunal Hazard

Answer 6

所有其他答案似乎都是正确的。我只想再补充一点。我认为在双向链表中，如果您有该节点的引用，则删除任何节点的时间复杂度将为O(1)。由于它是双向链表，并且您手头有节点的引用，因此您可以直接更新前一个节点的指针，因此使用引用删除节点仅需要花费O(1)的时间。由于双向链表的属性，您不需要遍历，因此使用引用删除节点的时间复杂度将为O(1)。

您可以在这里阅读更多信息：双向链表元素删除的时间复杂度？

- Sukhbir