给定指针，从 LinkedList 集合中删除元素

Question

我有一个对象的LinkedList，以及一个指向我要删除的LinkedList对象的指针。

有一个方法remove(object o)，可用于删除对象，但正如文档所述，它会逐个检查所有元素，然后选择一个对象，这在语义上是相同的。

但是这种方法不符合我的要求。

由于我有一个指向要删除对象的指针，因此我应该能够在O(1)时间内删除它，因为LinkedList是一个双向链表。有没有其他方法可以在不实现我自己的LinkedList类的情况下做到这一点？

Answer 1

如果只有对对象本身的引用，则无法从 O(1( 中的LinkedList中删除对象。

如果通过在迭代器上调用remove()将ListIterator<E>对象定位在要删除的项上，则可以删除对象，但这没有多大帮助，因为迭代器将在修改列表的那一刻失效。

下面是如何保持删除 O(1( 的示例。不过，搜索仍然是 O(n(：

List<String> list = new LinkedList<>();
list.add("hello");
list.add("world");
list.add("one");
list.add("two");
list.add("three");
System.out.println(Arrays.toString(list.toArray()));
ListIterator<String> iter = list.listIterator();
String s;
while ((s = iter.next()) != null && !s.equals("world"))
;
// When it is time to delete
iter.remove();
System.out.println(Arrays.toString(list.toArray()));

由于ConcurrentModificationException，编写自己的LinkedList<E>实现并保留对节点的引用以供将来删除仍然是纯链表的最佳选择。

您的另一个选项是使用LinkedHashSet<E>，它提供可预测的枚举顺序和 O(1( 删除，以换取使用更多内存。

Answer 2

怎么样：

public void remove(Car searchedFor) {
for (Iterator<Car> it = list.iterator(); it.hasNext(); ) {
Car c = it.next;
if (c == searchedFor) {
it.remove();
}
}
}

Answer 3

解决我问题的一个很好的方法是同时使用List和HashSet。由于我们使用的是HashSet因此无法处理重复项。

插入：插入List和HashSet。O(1)时间。
删除：从HashSet中删除，如果存在。O(1)时间。遍
历：遍历List。仅当HashSet包含该对象时才访问。

请注意，我不想在这里复制LinkedList的工作。我只是分享对我有用的东西。