在 Java 中从 LinkedList 中删除一个元素的复杂性

Question

我不明白为什么在 Java 中删除 LinkedList 中的元素的复杂度是 O(n)。 Java 中的 LinkedList 是一个 DoublyLinkedList。在理想的 DoublyLinkedList 中，每个元素都有一个字段 prev 和 next 分别指向下一个和上一个元素。 现在，如果我考虑一个方法 remove(element)，唯一要做的就是更新前一个元素和下一个元素的 next 和 prev 字段。这是 O(1)。这是选择双向链表的好处。

我试图在内置 API 中搜索确保这种复杂性的实现，但我失败了。 Java API 中是否有允许在 O(1) 中删除的类？

Answer 1

指向上一个和下一个对象的链接不在对象本身中。在链表中，我们有一些节点链接到上一个、下一个和对象，为了找到这个节点，我们必须一个一个地检查每个节点。

Answer 2

如果你已经有了

element

，那么删除操作的时间复杂度确实是O(1)。

但是：

• Java的

  LinkedList

  类实现了一个双向链表，但是它的节点是私有的。 API 仅提供对链表中values 的访问，不提供对节点的访问。因此，您永远不会引用要删除的 element。

• 即使您使用替代实现，do 可以访问节点，您也可以仅从对head 节点的引用开始，而不是对列表中all 节点的引用数组。所以这意味着如果你想删除列表中的k^th节点，你必须先遍历列表来找到它。将该工作包含在删除k^th节点的工作中才公平。

您在评论中写道：

假设我有一个

LinkedList<Person> ll

，我有

Person p1

我想做

ll.remove(p1)

.

这不会像您希望的那样工作，因为

Person

没有上一个/下一个属性。当您创建

LinkedList<Person> ll

时，会涉及一个私有节点类，它 包含 对

Person

的引用，但另外还有那些上一个/下一个引用。

p1

无法帮助您访问那些上一个/下一个成员。您仍然需要遍历列表以找到哪个节点具有该特定

p1

，然后更新该节点。这就是 Java 的

removeFirstOccurrence

所做的。

Java 的

LinkedList

是否应该提供对节点的访问权限以获得更好的性能？

您可能认为 Java 选择将 Node 对象设为私有而不提供直接在这些节点上工作的方法是一个糟糕的选择，因为它似乎降低了列表上的某些操作的效率，但考虑一下：

• 如果您可以直接访问节点，您可能会不小心使列表在某种程度上“不一致”：您可以：

  1. 引入循环
  2. 链接到实际上是另一个列表一部分的节点，因此：
  3. 通过改变列表 A 来改变另一个列表 B。

• 即使这些效果在您的场景中是可以接受的，也要考虑到您没有直接引用链表中的each节点。如果您 would，那么您实际上得到了一个节点引用集合，您有额外的任务来管理该集合上的 CRUD 操作。例如，如果它是一个向量，那么删除该向量中的节点引用将是 O(n)。或者，如果它是一个 Map，您的节点需要唯一的键，而链表允许重复。

  无论那个集合是什么样的，它都会代表额外的开销，在某些情况下，你可能会决定删除链表并只保留那个集合。例如，使用 TreeMap 可以获取顺序，并且可以使用次线性方法来获取、设置和删除条目。