java - 在 O(n) 时间内遍历 LinkedList 并删除 k 个元素

Question

我用的是Java的LinkedList，据我所知，没有LinkedList.next(int);，但是有ListIterator.next ()，它通过 LinkedList.listIterator() 发挥作用。然而，正如我发现的那样:使用 ListIterator 遍历元素(这需要 O(n) 时间)将在你删除所有元素后失败(对删除本身的常量时间操作，但是O(n) 到达元素)。

尝试以直接的方式删除一些 k <= n 元素，类似于:

if (list.get(++index).equals(elementToRemove))
{
    list.remove(index);
}

是一个 O(n^2) 操作，因为 n 个 get() 中的每一个都是 O(n)。

有没有办法在线性时间内遍历 LinkedList 并删除应该去的元素？

Answer 1

使用Iterator.remove() :

for (Iterator<T> iterator = list.iterator(); iterator.hasNext(); ) {
    T element = iterator.next();
    if (element.equals(elementToRemove)) {
        iterator.remove();
    }
}