Removing elements on a List while iterating through it

Question

I needed a way to remove elements on a List while iterating through it.

Supposedly something like this (illegal code):

List<Integer> nums = new ArrayList();
nums.add(1);
nums.add(2);
nums.add(3);
...
nums.add(10);

System.out.println("BEFORE REMOVE: " + nums);

for (Integer integer : nums) {
    if (integer < 3) {
        //not allowed
        nums.remove(integer);
    }
}

But we all know that the above code is not allowed.

So what I'm doing right now is that I create another List, where I'm putting every element that meets a given condition, then iterate through that List to get the elements that I need to remove on the first List.

List<Integer> toRemove = new ArrayList();
for (Integer integer : nums) {
    if (integer < 3) {
        toRemove.add(integer);
    }
}

for (Integer integer : toRemove) {
    nums.remove(integer);
}

System.out.println("AFTER REMOVE: " + nums);

I know it's not really long, but is there a better way to do this?

Is there some API that I can use?

Answer 1

There are several ways to do this. Let's look at the alternatives:

Iterating over a copy, removing from original

This is a simple solution for the underlying problem of your first code: A ConcurrentModificationException is thrown because you iterate through the list and removing from it at the same time.

Easy solution is to create a copy of the list and iterate through that.

for (Integer integer : new ArrayList<>(nums)) {
    if (integer < 3) {
        nums.remove(integer);
    }
}

Down-sides of this approach:

• Creates a copy of the original list, which requires memory and an operation which performance depends on the type of the list (ArrayList, LinkedList, etc.)
• Additionally, nums.remove(value) is a \$O(n)\$ operation. Making this loop overall \$O(n^2)\$

Java 8 Streams

List<Integer> filteredList = nums.stream().filter(i -> i >= 3).collect(Collectors.toList());

Down-sides:

• Does not actually modify the existing list, so if references to the list are spread around various variables, you still have some old elements that just shouldn't be in that list.
• Creates various stream-related objects which might not be the most effective option.

On the up-side, this is among the fastest for bigger lists.

If you're not using Java 8:

List<Object> originalList;
List<Object> newList = new YourFavoriteListType<>();
for (Object obj : originalList) {
    if (shouldKeep(obj)) {
        newList.add(obj);
    }
}

Java 8 method

nums.removeIf(i -> i < 3);

Java 8 introduced the default method removeIf on the Collection interface. This allows different implementations to have implementation-specific performance-optimized implementations of this method.

Iterator.remove()

Iterator<Integer> it = nums.iterator();
while (it.hasNext()) {
    Integer integer = it.next();
    if (integer < 3) {
        it.remove();
    }
}

The only down-side of this approach is that you need to switch your for-each to a while. However, this approach is the most efficient one, especially for LinkedList where it is \$O(n)\$ (it's \$O(n^2)\$ for ArrayList because it has to copy array data on each remove(index) call). This is the approach I would recommend in most cases.

Note: Instead of using a while-loop it can also be written as:

for (Iterator<Integer> it = list.iterator(); it.hasNext(); ) {
    Integer integer = it.next();
    ...

Conclusion

If you want to mutate the existing list, removeIf is the solution I would go with. If you like functional programming and prefer a new list instead of mutating the existing one, then go with the list.stream().filter(...).collect(Collectors.toList()) approach.

See also

"When to use LinkedList over ArrayList?" on Stack Overflow

Answer 2

Just had to do something very similar (hence why I'm here), ended up using Java8's Collection.removeIf(Predicate<? super E> filter)

With your code it would look like:

nums.removeIf((Integer i)->{return i<3;});

And if you wanted to collect the removes:

List<Integer> removed = new ArrayList<>();
nums.removeIf(
    (Integer i)->{
        boolean remove = i<3;
        if (remove) {
            removed.add(i);
        }
        return remove;
    });

Answer 3

Out of the other presented solutions, all but the one using Java 8 seem to be O(n²), i.e., too slow when the list(*) gets a bit bigger.

The simplest fast solution is to create an empty list and add all elements not less than three.

If you need to modify the original list, then clean if afterwards and add all elements from the auxiliary list.

---

(*) Unless it's a LinkedList, which excels here. But its performance in all other scenarios is so terrible that it should be practically never used.

Answer 4

Another perhaps interesting option is using a CopyOnWriteArrayList:

@Test
public void testCanRemoveFromCopyOnWriteArrayList() {
    List<Integer> nums = new CopyOnWriteArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
    for (Integer num : nums) {
        if (num < 3) {
            nums.remove(num);
        }
    }
    assertEquals(Arrays.asList(3, 4, 5), nums);
}

The downside is obvious, from the name of the class: it copies the underlying list before every write operation. This class is designed for observer lists, which are rarely modified and often traversed. I'm not sure if this applies to your case (if deleting from the list will be frequent or not), but I thought I'd mention this just in case.

Answer 5

Adding to @Simon's answer, you could use a reversed for loop to go through your array to remove items you don't want. It remains an O(n^2) operation because of the remove method. So this approach isn't any better, but it's a different way to do it.

for(int index = array.size() - 1; index >= 0; index--) {
    if(array.get(index) < 3){
        array.remove(index);
    }
}