指向Java LinkedList节点的指针 [英] Pointer into Java LinkedList Node

问题描述

我正在O(1)将n个条目推送到Java LinkedList中.
我想稍后在O(1)删除一些独特的项目.
我虽然要在LinkedList上保留指向唯一"节点的带有指针"的数组，以便以后可以将其删除.
有没有办法在LinkedList或任何其他Java类上执行此操作?
我尝试将迭代器存储到项目.所以我可以使用iter.remove().但我知道当时列表上只能有一个迭代器.

I am pushing n entries into Java LinkedList at O(1).
There are few unique items i would like to remove later on at O(1).
I though about keeping an array with "pointers" to the unique nodes at the LinkedList so i can later on remove them.
is there a way to do it on LinkedList or any other java class?
I tried storing iterators to the items. So i can use iter.remove(). But i understood that there can be only one iterator on a list at the time.

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

I know that an easy solution could be implementing link list on my own. But i rather use LinkedList or some other Java class already implemented.

推荐答案

Java List实现在removes *上不提供O(1)性能.使用迭代器，您必须遍历索引(O(n))，使用ArrayList进行删除后移位(O(n))，即使LinkedList是双向链接列表，它不会通过简单地重新分配下一个/最后一个引用来公开删除列表中的节点，而是需要遍历才能找到要删除的节点(O(n)).

The Java List implementations do not offer O(1) performance on removes*. Using an iterator you have to traverse to the index ( O(n) ), with an ArrayList you have an after-remove shift ( O(n) ), and even though LinkedList is a doubly-linked list, it does not expose the nodes in the list for you to be able to remove them directly by simply reassigning the next/last references - a traversal is required to find the node to remove ( O(n) ).

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

You could write your own MyDoublyLinkedList<MyNode<T>> that did so, exposing the nodes rather than the values contained within, which would allow for O(1) removals if you retained a reference to the node. Indexing is of course O(n) to get something from the list by index. Depending on your use patterns it may be a viable design choice.

其中之一，如果要使用Java提供的数据结构，请使用可提供这种性能的数据结构:

Short of that, if you want to use the data structures provided by Java, use a data structure that provides that performance:

如果订购不重要且没有重复的项目，请使用哈希集(但是请注意，这根本不允许直接索引)

If ordering isn't important and there are no duplicate items, use a HashSet (note, however, this does not allow direct indexing at all)

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

Otherwise, reworking your code to use a Map implementation is probably your best bet.

[*] LinkedList和Deque的实现是O(1)，用于去除头/尾.

[*] LinkedList and the Deque implementations are O(1) for head/tail removal.

编辑以添加评论:

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

As mentioned above, no, there is no O(1) time complexity remove operation.

原因 在于，除了在最极端的情况下，它是无关紧要的.

The reason for this is that except in the most extreme edge cases, it's irrelevant.

在我5岁的3Ghz台式机上，通过索引(即index = length)在100,000个条目的LinkedList上，最坏情况下的O(n)移除需要0.2ms(第二点). /2)

On my 5 year old, 3Ghz desktop it takes .2ms (point-two) for the worst-case O(n) removal on a LinkedList with 100,000 entries via an index (that is to say, index = length/2)

由于此盒上的Windows内存管理，如果将其增加到1,000,000个条目，我将开始进入Windows交换磁盘I/O.

I start running into windows swapiness disk I/O due to windows memory management on this box if I up it to 1,000,000 entries.

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

In short, you're trying to solve a problem that doesn't exist in most cases. This is generally called "Premature Optimization"

这篇关于指向Java LinkedList节点的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！