如何高效地从Java LinkedList中移除一个元素。

Question

我有一个算法，按照一定的方式通过图中的节点，偶尔会多次经过同一个节点，并且我需要形成一个节点列表，使得每个节点仅出现在我最后一次经过它时。

例如，如果我通过节点 A -> B -> C -> A -> C，则最终需要的列表是 [B，A，C]。

我想做的是使用 LinkedList，以便图中的每个节点都包含对其在 LinkedList 中的节点的引用。然后，每次经过一个节点时，我将从 LinkedList 中删除其相应的节点，并将其重新插入到 LinkedList 的末尾，操作的复杂度仅为 O(1)。

然而，当我开始实现时，遇到了一个问题：显然，Java 类 LinkedList 不允许我查看其实际的列表节点。使用 LinkedList 的常规 remove 函数来删除包含给定图节点的列表节点将是 O(n)，而不是 O(1)，从而否定了使用 LinkedList 的初衷。

当然，我可以自己实现 LinkedList，但我宁愿避免这样做-我觉得如果我必须在 Java 中实现 LinkedList，那么我做错了什么。

因此，有没有一种方法可以在不实现自己的 LinkedList 的情况下解决此问题？我是否漏掉了什么东西？

- Nachshon Schwartz

---

你说得对，该API在那一点上确实很糟糕。LinkedList的内部工作方式不是公开的，甚至在时间上也不是恒定的。LinkedList内部的Node类名字已经随着时间的推移而改变了。我想你唯一的选择就是创建自己的类。你可以复制LinkedList源代码并根据需要进行修改。 - Martijn Courteaux

问题是，当重新插入元素时，你应该如何从列表中找到它？ - Sage

每个图节点都持有其列表节点的引用。当我通过图节点时，使用此引用从列表中删除该节点，然后将图节点插入列表末尾（并保存对新列表节点的引用，即插入到列表末尾的节点）。 - Nachshon Schwartz

@Sage 如果您将您的评论写成答案，我就能够给您帮助的功劳。 - Nachshon Schwartz

@Nayish，抱歉，实际上我认为你是对的，我应该将其发布为答案供未来可能会搜索的人使用。谢谢 :) - Sage

Answer 1

看起来，您希望有一个内置方法，但我不认为有任何集合提供这样的功能。如@MartijinCourteaux建议的那样，您将不得不自己实现它。或者：

• 使用 Sorted Set 集合，例如 TreeSet<E>，支持 O(log n) 的成本进行操作：add、remove 和 contains。
• LinkedHashSet<E>。但是请注意，与 HashSet<E> 不同，LinkedHashSet 可以在操作 add、contains、remove 时具有 O(1) 的预期性能，但由于维护链表的额外开销，性能可能略低于 HashSet。但我们可以在不产生与 TreeSet 相关的增加成本的情况下使用它。然而，如果将元素重新插入集合中，则不会影响插入顺序，请尝试在重新插入元素之前删除第一次插入的元素。

- Sage

Answer 2

LinkedHashMap 保留输入值的顺序，并允许通过其键删除节点，然后将其放回到末尾。我认为这就是你所需要的。

- JosefN

Answer 3

除非你的链表很大，否则仅使用常规数组列表即可在洗牌时获得快速性能。如果顺序不重要，您还应考虑使用哈希集，如果插入顺序很重要，则使用链接哈希集，或者如果您想要排序，则使用树集。它们不允许重复值，但对于插入、删除和包含操作具有良好的O性能。

- Tim B