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不需要任何查找，因为它在迭代时维护一个指向节点的指针。因此它已经掌握了您要删除的节点。