Java：从链表中查找和删除元素的最佳方法

Question

我想知道这个问题已经有一段时间了，但还没有找到一个很好的答案。

我想做的是在链表中找到一个元素并立即删除它。如果我自己构造链表，那会很容易，因为我只是遍历双向链表：

-> N1 <-> N2 <-> N3 <-> N4 <-> N5 <-

当你发现例如N3，您更改 node.previous 和 node.next 指针，使得：

-> N1 <-> N2 <-> N4 <-> N5 <-

如果元素在中间，这将需要大约 n/2 个步骤。

在 java.util.LinkedList<Integer> 中是否有正确的方法来做到这一点？

一种对我来说不够的方法是：

Integer found = null;
for(Integer elem : list){
    if(hasCertainProperty(elem)){
        found = elem;
    } 
}
if(found != null){
    list.remove(found);
}

如果该元素是列表的中间元素（双链表，因此如果索引已知，理论上可以从列表末尾搜索），则最多需要大约 n/2 + n/2 = n 步。而在自制遍历中，它只需要 n/2 步。

我知道这 2 种方法和其他方法的复杂度为 O(n)，但您知道，有时 n/2 在实践中会有所不同。

感谢您的帮助。

Answer 1

Java 8 会为您做这件事。

list.removeIf(x -> hasCertainProperty(x));

这会在列表内部循环，检查每个项目 x 是否满足您的条件 hasCertainProperty，然后删除该项目。我想你不应该关心性能。 Java 会为您处理。

除此之外，您应该使用正是为此目的而制作的 ListIterator。您可以使用 LinkedList#listIterator:

获取它

ListIterator<Integer> listIter = list.listIterator(0);
while (listIter.hasNext()) {
    Integer element = listIter.next();

    if (hasCertainProperty(element)) {
        listIter.remove();
        break;
    }
}

它的 remove 不需要任何查找，因为它在迭代时维护指向节点的指针。所以它掌握了你要删除的节点。

Java：从链表中查找和删除元素的最佳方法

Java: best way to find and remove an element from linked list

java

linked-list

doubly-linked-list