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

Question

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

有一种方法remove(object o)，可以用来删除一个对象，但是正如文档所描述的，它会一个一个地检查所有元素，并选择一个对象，也就是语义相同。

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

因为我有一个指向我要删除的对象的指针，所以我应该能够在 O(1) 时间内删除它，因为 LinkedList 是一个双向链表。 如果不实现我自己的 LinkedList class，还有其他方法吗？

Answer 1

怎么样：

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

Answer 2

如果您只有对对象本身的引用，则无法在 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 3

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

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

请注意，我并不是要在此处复制 LinkedList 的工作原理。我只是分享对我有用的东西。

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

Given the pointer, deleting an element from a LinkedList collection

java

collections

linked-list

doubly-linked-list