指向Java LinkedList节点的指针

Question

我LinkedList在O(1)处将n个条目推入Java .
我希望稍后在O(1)删除几个独特的项目.
我虽然要保留一个带有"指针"的数组,LinkedList但是我可以稍后删除它们.
有没有办法在LinkedList任何其他java类上执行此操作？
我尝试将迭代器存储到项目中.所以我可以使用iter.remove().但我明白当时列表中只能有一个迭代器.

我知道一个简单的解决方案可能是我自己实现链接列表.但我宁愿使用LinkedList或已经实现的其他Java类.

Answer 1

Java List实现不提供O(1)remove*的性能.使用迭代器,你必须遍历索引(O(n)),ArrayList你有一个删除后的移位(O(n)),即使LinkedList是一个双向链表,它也不会暴露节点通过简单地重新分配下一个/最后一个引用,您可以直接删除它们的列表 - 需要遍历才能找到要删除的节点(O(n)).

您可以自己编写MyDoublyLinkedList<MyNode<T>>这样做,暴露节点而不是其中包含的值,如果您保留对节点的引用,则允许O(1)删除.索引当然是O(n)从索引列表中获取内容.根据您的使用模式,它可能是一个可行的设计选择.

如果您想使用Java提供的数据结构,请使用提供该性能的数据结构:

如果排序不重要且没有重复项,请使用HashSet(但请注意,这根本不允许直接索引)

否则,重新编写代码以使用Map实现可能是您最好的选择.

[*] LinkedList并且Deque实现是用于头/尾移除的O(1).

编辑以添加评论:

如上所述,不,没有O(1)时间复杂度删除操作.

这样做的原因是,除了在最极端的情况下,它是无关紧要的.

在我5岁的3Ghz桌面上LinkedList,通过索引获取100,000个条目的最坏情况O(n)删除需要.2ms(第二点)(也就是说,index = length/2)

我开始运行Windows交换磁盘I/O,因为这个盒子上的Windows内存管理,如果我把它增加到1,000,000个条目.

简而言之,您正在尝试解决大多数情况下不存在的问题.这通常被称为"过早优化"