本文介绍了指向 Java LinkedList 节点的指针的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我在 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 实现在移除时不提供 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(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:

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

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.

[*] LinkedListDeque 实现是 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 桌面上,通过索引(即比如说,索引 = 长度/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)

如果我将它增加到 1,000,000 个条目,由于此框上的 Windows 内存管理,我开始遇到 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 节点的指针的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-22 17:26