我正在以 O(1) 的时间将 n 个条目推送到 Java LinkedList。
稍后我想在 O(1) 时删除一些独特的项目。
我想保留一个数组，其中包含指向 LinkedList 中唯一节点的“指针”，以便稍后删除它们。
有没有办法在 LinkedList 或任何其他 java 类上做到这一点？
我尝试将迭代器存储到项目中。所以我可以使用 iter.remove()。但我知道当时列表上只能有一个迭代器。
我知道一个简单的解决方案是自己实现链接列表。
但我宁愿使用 LinkedList 或其他一些已经实现的 Java 类。
最佳答案
Java List实现不提供 O(1)删除时的性能*。使用迭代器，你必须遍历到索引( O(n) )，带有 ArrayList你有一个删除后的类次( O(n) )，即使 LinkedList是一个双向链表，它不会公开列表中的节点，您可以通过简单地重新分配下一个/最后一个引用来直接删除它们 - 需要遍历才能找到要删除的节点( O(n) ) .
你可以自己写MyDoublyLinkedList<MyNode<T>>这样做会暴露节点而不是其中包含的值，如果您保留对节点的引用，这将允许 O(1) 删除。索引当然是 O(n) 通过索引从列表中获取一些东西。根据您的使用模式，它可能是一个可行的设计选择。
除此之外，如果您想使用 Java 提供的数据结构，请使用提供该性能的数据结构:
如果排序不重要并且没有重复项，请使用 HashSet (但是请注意，这根本不允许直接索引)
否则，重新编写代码以使用 Map实现可能是您最好的选择。
[*] LinkedList和 Deque去除头/尾的实现是 O(1)。
编辑以从评论中添加:
如前所述，不，不存在O(1)时间复杂度的remove操作。
这样做的原因是，除了在最极端的情况下，它是无关紧要的。
在我 5 岁的 3Ghz 台式机上，在 LinkedList 上最坏情况下的 O(n) 删除需要 .2 毫秒(第二点)通过索引有 100,000 个条目(也就是说，索引 = length/2)
如果我将其增加到 1,000,000 个条目，由于此框上的 Windows 内存管理，我开始遇到 Windows Swapiness 磁盘 I/O。
简而言之，您正在尝试解决在大多数情况下不存在的问题。这通常被称为“过早优化”
关于java - 指向 Java LinkedList 节点的指针，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21294241/