Remove first N occurrence of an element from a List

Question

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?

Answer 1

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).