java - 如何有效地从java LinkedList中删除一个元素

Question

我有一个算法，我以某种方式通过图中的节点，偶尔会多次通过同一个节点，我需要形成一个通过的节点列表，这样一个节点最后出现一次我通过它的时间。

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

我想做的是使用 LinkedList，这样图中的每个节点都将包含对其在 LinkedList 中的节点的引用。然后，我每经过一个节点，就将其对应的节点从LinkedList中移除，重新插入到LinkedList的尾部，操作的复杂度只会是O(1) .

但是，当我开始实现它时，我遇到了一个问题:显然，java 类 LinkedList 不允许我看到它的实际列表节点。使用 LinkedList 的常规删除函数删除包含给定图形节点的列表节点将是 O(n) 而不是 O(1)，否定了使用 a 的全部意义链表开始。

当然，我可以自己实现 LinkedList，但我宁愿避免这种情况 - 在我看来，如果我必须在 java 中实现 LinkedList，我做错了什么。

那么，有没有办法不用自己实现LinkedList就可以解决这个问题呢？有什么我想念的吗？

Answer 1

看起来，您期待的是一种内置方法，我认为没有任何 Collection 提供此类功能。您必须按照@MartijinCourteaux 的建议自行实现。或者:

• 使用像 TreeSet<E> 这样的 Sorted Set 集合配套费用为 O(log n)用于操作:add, remove and contains .
• LinkedHashSet<E> 但要注意不像 HashSet<E> , LinkedHashSet可以有O(1)操作的预期性能:add, contains, remove但性能可能略低于 HashSet 的性能，由于维护链表的额外费用。但是我们可以使用它而不会增加与 TreeSet 相关的成本。 .但是，如果将元素重新插入到集合中，插入顺序不会受到影响，因此请尝试在重新插入元素之前删除第一个插入的元素。