我不明白为什么在Java中删除LinkedList中的元素的复杂性是O(n)。Java中的LinkedList是DoublyLinkedList。在理想的DoublyLinkedList中，每个元素都有一个字段prev和next，分别指向下一个和上一个元素。现在，如果我考虑一个方法remove(element)，唯一要做的就是更新前一个和下一个元素的next和prev字段。这是O(1)这是选择双链表的好处。
我试图在内置API中搜索一个保证这种复杂性的实现，但我失败了。Java API中是否有允许在0(1)中删除的类?
指向prev和next对象的链接，而不是在对象本身中。在linkedlist中，我们有一些节点链接到prev, next和object，为了找到这个节点，我们必须一个一个地检查每个节点。
如果您已经有了element，那么删除操作的时间复杂度确实为0(1)。
但:
-
Java的
LinkedList类实现了一个双重链表，但是它的节点是私有的。API只提供对链表中的值的访问，而不提供对节点的访问。所以你永远不会有对元素的引用来删除。 -
即使您使用可以访问节点的替代实现，您也只能从对头部节点的引用开始，而不是对列表中所有节点的引用数组。因此，这意味着如果您想要删除列表中的k节点，则必须首先遍历列表以定位它。只有在删除k节点的工作中包含该工作才是公平的。
您在评论中写道:
假设我有一个
LinkedList<Person> ll，我有一个Person p1，我想做ll.remove(p1)。
这不会像你希望的那样工作，因为Person没有prev/next属性。当您创建LinkedList<Person> ll时，涉及到一个私有节点类，其中包含对Person的引用，但除此之外还有那些prev/next引用。p1并不能帮助你访问那些previous/next成员。您仍然需要遍历列表以查找具有特定p1的节点，然后更新该节点。这就是Java的removeFirstOccurrence所做的。
Java的LinkedList是否应该允许访问节点以获得更好的性能?
您可能认为Java选择使Node对象私有并且不提供直接在这些节点上工作的方法是一个糟糕的选择，因为它似乎使列表上的一些操作效率降低，但是考虑一下:
-
如果您可以直接访问节点，您可能会意外地使列表"不一致"。在某种程度上:你可以:
<<ol> - 介绍周期/gh>链接到一个节点，该节点实际上是另一个列表的一部分，因此:
- 通过改变列表a来改变另一个列表B
-
即使这些效果在您的场景中是可以接受的，那么请考虑您没有直接引用每个链表中的节点。如果您将，那么您最终会得到一个节点引用集合，在这个集合上您有额外的任务来管理CRUD操作。例如，如果它是一个向量，那么删除该向量中的节点引用将是O(n)。或者，如果是Map，则需要节点的唯一键，而链表允许重复。
无论该集合是什么样子，它都将代表额外的开销，在某些情况下，您可能会决定删除链表并仅保留该集合。例如，使用TreeMap，您可以获得顺序，并且可以使用次线性方法来获取、设置和删除条目。