Java通过引用删除链表中的节点

Question

如何通过对对象的引用或特定节点从Java的LinkedList 中有效地删除节点？使用remove（object）会对整个列表进行遍历，这在文档中有所体现：“删除第一个元素e，使得（o==null ? e==null : o.equals(e))”。我可以通过节点的具体引用来移除吗？我不介意将节点的引用存储在对象本身中。我不能使用列表的索引，因为它可能会改变。如果不行，是否有其他数据结构可以实现此操作？

- user3473949

---

你需要为你的节点使用指针吗？ - zgc7009

你自己的链表？内置的 LinkedList？如果是你自己实现的，那就取决于你的实现方式。你尝试过什么？能否发布相关代码并描述你遇到的问题？至于其他数据结构，它取决于你的需求。你必须更具体地说明。 - Jason C

Answer 1

您可能想使用一个 HashSet。

通常情况下，删除和插入操作的时间复杂度都是常数级别的，正如官方API所述：

“假设哈希函数将元素正确地分散在桶中，此类提供基本操作（添加、删除、包含和大小）的常数时间性能。”

如果您决定使用HashSet，请不要忘记在您的对象中同时重写equals和hashcode方法。

- cheseaux

---

我曾考虑过使用 HashSet，但我需要保留插入顺序。此外，哈希似乎是一种变通方法，而我想直接通过引用访问。 - user3473949

在这种情况下，正如@tskuzzy所回答的那样，您需要使用LinkedHashSet。但是哈希不是“变通方法”。 - cheseaux

Answer 2

尝试使用LinkedHashSet。它基本上是一个HashSet，其元素具有确定性顺序。或者，您可以将其视为由元素查找表支持的LinkedList。

我相信remove(Object)操作将是常数时间。

- tskuzzy

---

谢谢，这非常接近我想要的。然而，哈希仍然似乎是一种解决方法，而我想直接通过引用访问。 - user3473949

HashSet不允许重复项。您可能需要定义equals和hashCode方法时考虑到这一点。如果迭代性能很关键，您还需要注意初始容量。 - hellboy