问题描述
我正在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节点的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！