Remove first N occurrence of an element from a List

user_3555445 0
Viewed 1037

Java 8 introduced Lambdas, which allow us to efficiently remove all elements from a List. The following removes all instances of 2 from myList.

List<Integer> myList;
...
myList.removeIf(x -> x==2);

If I wanted to remove N number of elements (in this case, three), I would use a for loop.

for (int i = 0; i < 3; i++) {
    myList.remove(Integer.valueOf(2));
}

Is there a way to remove a specified number of elements from a List using Lambdas? If so, is it more efficient than the for loop code?

java-8 lambda java
4 Answers

When you repeatedly call remove(Object) you get O(n²) time complexity from both, starting the search repeatedly from the beginning (applies to all List types) and from repeatedly copying the elements after the removed one, when the list is an ArrayList or similar.

The time complexity of the search can be avoided by using a dedicated search and remove loop, e.g. using an Iterator and its remove method. But the copying time complexity remains, unless you use removeIf and the list class overrides it with an appropriate implementation (as ArrayList does).

One way of utilizing this advantage for removing n matches would be

int n = 3;
int last = IntStream.range(0, myList.size())
    .filter(ix -> myList.get(ix) == 2)
    .limit(n)
    .reduce((a,b) -> b)
    .orElse(-1);
myList.subList(0, last + 1).removeIf(x -> x == 2);

It’s more complicated and for small lists, it will be more expensive. However, for really large lists where the time complexity matters, it will benefit from the O(n) time complexity.

Note that when the predicate is a simple match operation, you can also use, e.g. removeAll(Collections.singleton(2)) instead of removeIf(x -> x == 2).

user_27114880

You can do something close to a for-loop:

IntStream.range(0,3).forEach(a-> integers.remove(Integer.valueOf(2)));

It should be equivalent to a for-loop in terms of performance.

user_133128200

Using lambdas:

Runnable runnable = () -> {
    for (int i = 0; i < 3; i++) {
        myList.remove(Integer.valueOf(2));
    }
};
runnable.run();

Just kidding.

user_7063170

A bit dirty, but requires just one pass:

public static <T extends Comparable<? super T>> List<T> removeFirstN(List<T> list, T t, int N) {
    int[] a = {0};
    return list.stream().filter(p -> !p.equals(t) || ++a[0] > N).collect(toList());
}
user_52794240
Related