Java链表支持快速删除任意节点？
java.util.LinkedList 不允许您快速删除列表中的给定对象。 remove(object) 方法执行线性搜索以查找列表中的对象，以便将其删除。由于这是一个双链表，因此最好通过更新指针（node.prev 和 node.next）来删除。
这个问题的Java标准解决方案是什么？
注意1：我不想在迭代时删除。我知道这很快，但我一开始就没有迭代我的元素。
注意2：为了简单起见：给定一个对象 O，我知道它位于双链表中，我想快速从该列表中删除 O（通过更新指针），而不必在列表中线性搜索它，如下所示java.util.LinkedList 确实如此。
The java.util.LinkedList does not allow you to quickly remove a given object in the list. The remove(object) method performs a linear search to find the object in the list so it can remove it. Since this is a double linked-list, it would be nice to remove by just updating the pointers (node.prev and node.next).
What is the Java standard solution for this problem?
NOTE1: I don't want to remove while iterating. I know that is fast, but I am not iterating through my elements in the first place.
NOTE2: To make it simple: Given an object O that I know it is in a double linked-list, I want to quickly remove O from that list (by updating the pointers) without having to linear search for it in the list, as java.util.LinkedList does.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
您应该查看 LinkedHashSet 类。基本上它是一个 HashSet，在其条目之间维护一个双向链表。它支持在 O(1) 中检索（因此也删除）元素（希望如此）。检查有关在重新插入条目和其他详细信息的情况下如何处理元素顺序的规范的链接。
编辑：
如果您需要存储重复项，可以查看Guava LinkedHashMultiset（到目前为止从未使用过）。 Multiset 上的 Guava 用户指南位于此处。
You should take a look at the LinkedHashSet class. Basically it's a HashSet that maintains a doubly-linked list among its entries. It supports retrieval (and thus also deletion) of an element in O(1) (hopefully). Check the link for the specification on the how it handles the elements order in case of reinserting an entry and other details.
EDIT:
If you need to store duplicates you can take a look at the Guava LinkedHashMultiset (never used so far). The Guava user guide on Multiset is here.
我敢打赌，
LinkedList#remove()的实现确实会通过更新指向上一项和下一项的指针来删除它 - 问题是，它必须循环所有对象，直到找到正确的对象删除。如果您想要一个删除速度更快的集合，而不需要迭代所有对象，请使用
Set或Map。I bet you that the implementation of
LinkedList#remove()does remove it by updating the pointers to the previous and next items - the problem is, it has to loop over all objects until it finds the proper one to remove.If you want a collection that removes faster, without iterating over all the objects, use a
Setor aMap.听起来您需要一个复合对象。创建一个包含列表的类，同时维护该列表的索引。
因此，当想要进行快速删除时，您需要进行恒定时间索引查找，以获取对要删除的列表元素的引用，然后进行恒定时间删除。
It sounds like you need a composite object. Create a class that contains your list, while also maintaining an index into that list.
So when wanting to do a fast remove, you do a constant time index lookup, to get a reference to the list element you wish to remove, followed by a constant time removal.
我主要是一名学习 Java 的 C 程序员。我找到这个线程是因为我还想知道为什么没有链表实现，您可以直接删除对象而无需搜索它。线性搜索效率极其低下。由哈希表支持的列表更好，但您并不真正知道哈希表将如何执行。
在 C 中可以轻松做到这一点的原因是因为通常列表元素对象本身包含下一个和上一个指针，因此给定该对象，操作几个指针以从列表中删除元素是一个简单的问题，所以它是一个O(1) 操作。在 Java 中，您拥有对象，但无法直接访问指针，因为它们在列表中单独维护。因此，您必须线性或使用哈希表来搜索对象。
似乎可以通过创建一个链表实现来解决这个问题，其中添加到列表中的每个对象类型都必须实现一个 LinkedListElement 接口，该接口支持获取和设置下一个和上一个指针。您必须向您的类添加下一个和上一个指针，并实现获取和设置它们的函数。然后，链接列表类将能够轻松删除对象，因为该对象本身包含指针。
I'm primarily a C programmer learning Java. I found this thread because I was also wondering why there was no linked list implementation where you could just remove the object directly without searching for it. Searching linearly is incredibly inefficient. A list backed with a hash table is better, but you don't really know how the hash table is going to perform.
The reason you can do this easily in C is because normally the list element object itself contains the next and previous pointers, so given the object, it's a simple matter of manipulating a couple of pointers to remove the element from the list, so it's an O(1) operation. In Java, you have the object, but you don't have direct access to the pointers because they are maintained separately within the list. Thus, you have to search for the object either linearly or with a hash table.
It seems like one could solve this problem by creating a linked list implementation where every object type added to the list would have to implement a LinkedListElement interface which would support getting and setting the next and previous pointers. You would have to add next and previous pointers to your class and implement the functions to get and set them. The links list class would then be able to easily remove an object because the object itself contains the pointers.
一般来说，您希望使用
ListIterator< /code>尽可能。它的remove将是常数时间。Java标准库没有单独的链表节点结构，所以我认为
ListIterator是最好的选择。Generally, you want to work using the
ListIteratorwhere possible. It'sremovewill be constant time.The Java standard library does not have a separate linked list node structure, so I think
ListIteratoris the best option.也许一张地图比较合适。它提供预期 O(1) 移除时间。但话又说回来，您没有具体说明快速的含义。
由 BST 支持的列表也可以发挥作用。它将给出 log(n) 移除时间。
对于此处列出的解决方案，我假设有比迭代列表更快的解决方案，因此任何比 O(n) 更快的解决方案；
Perhaps a map would be appropriate. It gives expected O(1) removal time. But then again you didn't specify what fast means.
A list backed by a BST could also work. It would give log(n) removal time.
For the solutions listed here I assumed something faster that iterating through the list, so anything faster than O(n);