In this post, we will see how to remove elements from a mutable list that satisfies the given condition within a loop or iterator.
It is tricky to add or remove elements from a list within a loop as index of its elements and the length of the list is changed. Consider below example, where we’re creating a list of colors and calling filterList() method that is supposed to remove elements from the specified list that has "RED" color.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
List<String> colors = new ArrayList<>(); colors.add("BLUE"); colors.add("RED"); colors.add("RED"); colors.add("YELLOW"); filterList(colors, new Predicate<String>() { @Override public boolean test(String t) { return "RED".equals(t); } }); } |
1. Incorrect output
There are two instances of "RED" color in the original list but below code will only remove first instance of "RED". The second "RED" is skipped because it is adjacent to the first "RED" and once first "RED" is removed, the list ordering is changed and second "RED" takes place of the first "RED", but index of the list also gets incremented by 1 which now points to "YELLOW" color.
In other words, when the i’th element of the list is removed, the element positioned at next index becomes the new i’th element. Now in the next iteration of the for-loop, since index i gets incremented, the unprocessed i’th element will be skipped.
|
1 2 3 4 5 6 7 8 9 10 11 |
public static <T> void filterList(List<T> list, Predicate<T> condition) { for (int i = 0; i < list.size(); i++) { if (condition.test(list.get(i))) { list.remove(i); } } System.out.println(list); // [BLUE, RED, YELLOW] } |
2. ConcurrentModificationException
It is not permissible to modify a list while iterating over it else a ConcurrentModificationException will be thrown to avoid non-deterministic behavior at later stage. For example, consider below methods which throws a ConcurrentModificationException as they permit concurrent modification:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public static <T> void filterList(List<T> list, Predicate<T> condition) { Iterator<T> itr = list.iterator(); // Using an Iterator while (itr.hasNext()) { T t = itr.next(); // throws ConcurrentModificationException if (condition.test(t)) { list.remove(t); } } } |
or using for-each loop (which internally uses an iterator):
|
1 2 3 4 5 6 7 8 |
public static <T> void filterList(List<T> list, Predicate<T> condition) { for (T t : list) // throws ConcurrentModificationException { if (condition.test(t)) list.remove(t); } } |
Workaround::
1. Iterating Backwards
We have seen that moving forward in the list using a for-loop and removing elements from it might cause to skip few elements. One workaround is to iterate backwards in the list, which does not skip anything.
|
1 2 3 4 5 6 7 8 9 10 11 |
public static <T> void filterList(List<T> list, Predicate<T> condition) { for (int i = list.size() - 1; i >= 0 ; i--) { if (condition.test(list.get(i))) { list.remove(i); } } System.out.println(list); // [BLUE, YELLOW] } |
2. Decremeting index
We can also decrement index i in the loop when the i’th element is removed from the list. Now i’th element will not be skipped.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public static <T> void filterList(List<T> list, Predicate<T> condition) { for (int i = 0; i < list.size(); i++) { if (condition.test(list.get(i))) { list.remove(i); i--; } } System.out.println(list); // [BLUE, YELLOW] } |
3. Iterator.remove()
We have seen that a ConcurrentModificationException will be thrown if we try to modify a list while iterating over it. The solution is to use iterator’s own remove method which removes the last element returned by the iterator.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Generic function to remove elements from a list in java public static <T> void remove(List<T> list, Predicate<T> condition) { Iterator<T> itr = list.iterator(); while (itr.hasNext()) { T t = itr.next(); if (condition.test(t)) { itr.remove(); } } System.out.println(list); // [BLUE, YELLOW] } |
Suggested Read: Remove Elements from a List that satisfies given predicate in Java
Thanks for reading.
Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply