java - 从 O(1) 中的链表中删除任何元素 - Java 与 C++

Question

在 C++ 中，我有时会将对象存储在链表中。我会将对象与指向其位置的迭代器相关联。然后，给定迭代器，我可以在 O(1) 时间内从链表中删除对象。该操作是 O(1)，因为列表只是更新指向列表中的前一个和下一个元素的指针。我正在谈论的 C++ 方法:http://www.cplusplus.com/reference/list/list/erase/

有没有办法在 Java 中以相同的 O(1) 复杂度做到这一点？

LinkedList 似乎转移了后续元素:https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html#remove(int)

也许有不同的 Java 类来实现这一点？

谢谢

Answer 1

标准库 LinkedList 不允许您这样做。 remove(int) 不需要移动元素，但它确实需要找到要删除的列表节点，这需要线性时间。您可以使用迭代器，但 Java 迭代器失效比 C++ 迭代器失效更激进。通过位于该元素的迭代器移除一个元素后，任何其他迭代器都将失效。

您可能必须编写自己的 LinkedList 类。