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

Question

据说 LinkedList 删除和添加操作的复杂性为 O（1）。在 ArrayList 的情况下，它是 O（n）。

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

现在，大小为“M”的LisnkedList：由于我们无法直接访问LinkedList中的第N个元素，为了访问第N个，我们必须遍历N个元素。因此，LinkedList的搜索成本比ArrayList高……但如果是LinkedList，Remove和add操作被称为O（1），因为LinkedList不涉及Shift，但是否涉及遍历操作？因此复杂性应该是O（n）阶，其中最差性能将在尾部节点，而最佳性能将在头部节点。

有人能解释一下为什么我们在计算LinkedList remove操作的复杂度时不考虑遍历成本？

所以我想了解一下它在java.util包中是如何工作的。如果我想在C或C中实现同样的功能，我如何在LinkedList中实现随机删除和插入的O(1)呢？

Answer 1

是的，如果你一次考虑两个操作(索引和插入),你是正确的。在这种情况下不成立，因为当你在一个链表的中间插入一个节点时，假设你已经在你要插入节点的地址了。

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

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

newnode->next = head;
head = newnode;

尾部插入要求您保留指向尾部元素的指针，在尾部添加元素并更新尾部指针。

tail->next = newnode;
tail = newnode;

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

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;

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.

Answer 3

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

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

这同样适用于无参数的< code>remove和< code > remove first /< code > remove last 方法——它们在列表末尾操作。

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