从链表中删除一个元素的大O表示法

Question

我在阅读关于链表的内容。我发现：从链表中删除一个特定元素需要O(n)的时间，其中n是链表中元素的数量。 http://www.cs.mcgill.ca/~dprecup/courses/IntroCS/Exams/comp250-final-2006-solutions.pdf 但在这个网页上，我发现从链表中删除一个元素的时间复杂度为: O(1)。 http://bigocheatsheet.com/ 以上哪一种大O符号是链表删除操作的正确时间复杂度呢？

谢谢！

- senshi nakamora

---

这要看你是要查找想要删除的元素还是已经有了该元素的引用（例如，如果你正在遍历列表并删除当前元素）。 - Eran

移除本身的时间复杂度为 O(1)，但是这个考试答案（出于某种原因？）还包括查找元素，时间复杂度为 O(n)。 - UnholySheep

https://dev59.com/P3RB5IYBdhLWcg3wpotm - Charmin

那就意味着当我删除一个项目时，我必须进行O(n)的搜索，然后进行O(1)的删除，所以总共是O(n)+O(1)=O(n)...是这样吗？谢谢。 - senshi nakamora

@senshinakamora 是的，删除一个节点的时间复杂度是常数 O(1)，与列表中的节点数量无关。然而，找到要开始的节点是 O(n)，取决于列表中的节点数量（线性搜索）。 - d.j.brown

Answer 1

从链表中删除项目所需的时间取决于我们如何准确地执行此操作。以下是可能性：

- 根据值删除。在这种情况下，我们需要查找（O(n)）并删除（O(1)）项。总时间为O(n)。 - 根据索引删除。在这种情况下，我们需要遍历列表（O(index)）并删除项（O(1)）。总时间为O(index)。对于任意索引，它是O(n)。 - 根据包含项目的链表节点的引用进行删除，O(1)。

在Java中，当您使用Iterator.remove或ListIterator.remove时，会出现最后一种情况。

- kgeorgiy

Answer 2

需要找到要删除的元素。这种查找相对较慢，因为在最坏的情况下，必须遍历整个列表才能找到该项。删除本身很便宜。因此，查找是O(n)，删除是O(1)。这只是一个理论问题吗？

- Stimpson Cat

Answer 3

链表的特点：

1. 获取操作的时间复杂度为O(n)
2. 添加操作的时间复杂度为O(1)
3. 查找操作的时间复杂度为O(n)
4. 下一个元素的访问时间复杂度为O(1)
5. 已知要删除的元素，删除操作的时间复杂度为O(1)

请参考下面的图片：

- ΦXocę 웃 Пepeúpa ツ

---

remove(O) 是什么？LinkedList() 有 remove(), remove(Object) 和 remove(int)。无参的 remove() 移除第一个元素，我期望它的时间复杂度是 O(1)。另外两个方法的时间复杂度应该是 O(n)，因为如你所说，要移除的元素还没有被找到。 - Ole V.V.

@OleV.V. remove(0) 是在移除列表的第一个元素。 "无参 remove 移除第一个元素，我希望它是 O(1)" - 并且在上面的表格中 LinkedList 的行是 O(1)。 "另外两个应该是 O(n)" - 并且它们是 O(n)。 "因为，正如你所说，要删除的元素尚未找到。" - 不正确，在 ArrayList 中需要移动所有元素，而在 CopyOnWriteArrayList 中需要复制整个数组。 - Jaroslaw Pawlak

哦，这是数字零，不是大写字母。谢谢解释。我只是在谈论LinkedList方法的实现，意思是LinkedList.remove(Object)和LinkedList.remove(int)都是O(n)，所以我想我们完全同意。 - Ole V.V.