指向Java LinkedList节点的指针

我在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实现可能是您最好的选择。

[*] LinkedListDeque实现是O(1)用于头部/尾部去除。

编辑以添加评论:

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

其原因是,除了在最极端的情况下,它是无关紧要的。

在我5岁的3Ghz桌面上,通过索引(即index = length / 2), LinkedList上最糟糕的O(n)删除需要0.2ms(点二)

如果我将它提升到1,000,000个条目,我将开始运行到Windows交换磁盘I / O,因为此框上的Windows内存管理。

总之,你正试图解决大多数情况下不存在的问题。 这通常称为“过早优化”


存储指向要删除项目的指针的问题是,从链接列表中删除项目需要知道要删除的项目之前的项目。

LinkedList不是用于以低成本去除特定项目 - 您应该重新评估您使用的List(ArrayList在O(1)中删除)。 是否有任何理由你想要一个LinkedList?

链接地址: http://www.djcxy.com/p/18711.html

上一篇: Pointer into Java LinkedList Node

下一篇: AWS CloudWatch Alarms to multiple EC2 instances