Remove elements from collection while iterating

Question

AFAIK, there are two approaches:

1. Iterate over a copy of the collection
2. Use the iterator of the actual collection

For instance,

List<Foo> fooListCopy = new ArrayList<Foo>(fooList);
for(Foo foo : fooListCopy){
    // modify actual fooList
}

and

Iterator<Foo> itr = fooList.iterator();
while(itr.hasNext()){
    // modify actual fooList using itr.remove()
}

Are there any reasons to prefer one approach over the other (e.g. preferring the first approach for the simple reason of readability)?

Solution 1

Let me give a few examples with some alternatives to avoid a ConcurrentModificationException.

Suppose we have the following collection of books

List<Book> books = new ArrayList<Book>();
books.add(new Book(new ISBN("0-201-63361-2")));
books.add(new Book(new ISBN("0-201-63361-3")));
books.add(new Book(new ISBN("0-201-63361-4")));

Collect and Remove

The first technique consists in collecting all the objects that we want to delete (e.g. using an enhanced for loop) and after we finish iterating, we remove all found objects.

ISBN isbn = new ISBN("0-201-63361-2");
List<Book> found = new ArrayList<Book>();
for(Book book : books){
    if(book.getIsbn().equals(isbn)){
        found.add(book);
    }
}
books.removeAll(found);

This is supposing that the operation you want to do is "delete".

If you want to "add" this approach would also work, but I would assume you would iterate over a different collection to determine what elements you want to add to a second collection and then issue an addAll method at the end.

Using ListIterator

If you are working with lists, another technique consists in using a ListIterator which has support for removal and addition of items during the iteration itself.

ListIterator<Book> iter = books.listIterator();
while(iter.hasNext()){
    if(iter.next().getIsbn().equals(isbn)){
        iter.remove();
    }
}

Again, I used the "remove" method in the example above which is what your question seemed to imply, but you may also use its add method to add new elements during iteration.

Using JDK >= 8

For those working with Java 8 or superior versions, there are a couple of other techniques you could use to take advantage of it.

You could use the new removeIf method in the Collection base class:

ISBN other = new ISBN("0-201-63361-2");
books.removeIf(b -> b.getIsbn().equals(other));

Or use the new stream API:

ISBN other = new ISBN("0-201-63361-2");
List<Book> filtered = books.stream()
                           .filter(b -> b.getIsbn().equals(other))
                           .collect(Collectors.toList());

In this last case, to filter elements out of a collection, you reassign the original reference to the filtered collection (i.e. books = filtered) or used the filtered collection to removeAll the found elements from the original collection (i.e. books.removeAll(filtered)).

Use Sublist or Subset

There are other alternatives as well. If the list is sorted, and you want to remove consecutive elements you can create a sublist and then clear it:

books.subList(0,5).clear();

Since the sublist is backed by the original list this would be an efficient way of removing this subcollection of elements.

Something similar could be achieved with sorted sets using NavigableSet.subSet method, or any of the slicing methods offered there.

Considerations:

What method you use might depend on what you are intending to do

• The collect and removeAl technique works with any Collection (Collection, List, Set, etc).
• The ListIterator technique obviously only works with lists, provided that their given ListIterator implementation offers support for add and remove operations.
• The Iterator approach would work with any type of collection, but it only supports remove operations.
• With the ListIterator/Iterator approach the obvious advantage is not having to copy anything since we remove as we iterate. So, this is very efficient.
• The JDK 8 streams example don't actually removed anything, but looked for the desired elements, and then we replaced the original collection reference with the new one, and let the old one be garbage collected. So, we iterate only once over the collection and that would be efficient.
• In the collect and removeAll approach the disadvantage is that we have to iterate twice. First we iterate in the foor-loop looking for an object that matches our removal criteria, and once we have found it, we ask to remove it from the original collection, which would imply a second iteration work to look for this item in order to remove it.
• I think it is worth mentioning that the remove method of the Iterator interface is marked as "optional" in Javadocs, which means that there could be Iterator implementations that throw UnsupportedOperationException if we invoke the remove method. As such, I'd say this approach is less safe than others if we cannot guarantee the iterator support for removal of elements.

Solution 2

Old Timer Favorite (it still works):

List<String> list;

for(int i = list.size() - 1; i >= 0; --i) 
{
        if(list.get(i).contains("bad"))
        {
                list.remove(i);
        }
}

Benefits:

1. It only iterates over the list once
2. No extra objects created, or other unneeded complexity
3. No problems with trying to use the index of a removed item, because... well, think about it!

Solution 3

In Java 8, there is another approach. Collection#removeIf

eg:

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

list.removeIf(i -> i > 2);

Solution 4

Are there any reasons to prefer one approach over the other

The first approach will work, but has the obvious overhead of copying the list.

The second approach will not work because many containers don't permit modification during iteration. This includes ArrayList.

If the only modification is to remove the current element, you can make the second approach work by using itr.remove() (that is, use the iterator's remove() method, not the container's). This would be my preferred method for iterators that support remove().

Solution 5

Only second approach will work. You can modify collection during iteration using iterator.remove() only. All other attempts will cause ConcurrentModificationException.

View more solutions

Comments

[Haz]

Just curious, why do you create a copy of foolist rather than just looping through foolist in the first example?

[user1329572]

@Haz, So I only have to loop once.

[Puce]

Note: prefer 'for' over 'while' also with iterators to limit the scope of the variable: for(Iterator<Foo> itr = fooList.iterator(); itr.hasNext();){}

[Alexander Mills]

I didn't know while had different scoping rules than for

[Dave Griffiths]

In a more complex situation you might have a case where fooList is an instance variable and you call a method during the loop that ends up calling another method in the same class that does fooList.remove(obj). Have seen this happen. In which case copying the list is safest.

[Vikas Tawniya]

@AlexanderMills while doesn't have a different scope rule. It's just that in case of while, Iterator is being declared outside the loop itself and so it will have a broader scope, even though it is just being used inside loop.

[Fizz]

Since you've accepted the answer you've accepted you probably had an XY problem, since that answer (like a few other here) doesn't actually remove during iteration. And the answer to your nominal question is quite obvious if you think a bit about it: immediately visible effect vs delayed/deferred deletion. It's not just a matter of "style" or "readability".

[Colin D]

The first attempt iterates on a copy, meaning he can modify the original.

[user1329572]

"Iterator works faster". Anything to support this claim? Also, the memory footprint of making a copy of a list is very trivial, especially since it'll be scoped within a method and will garbage collected almost immediately.

[user1329572]

Oops, sorry...it is implied that I would use the iterator's remove method, not the container's. And how much overhead does copying the list create? It can't be much and since it's scoped to a method, it should be garbage collected rather quickly. See edit..

[Edwin Dalorzo]

@aix I think it is worth mentioning the the remove method of the Iterator interface is marked as optional in Javadocs, which means that there could be Iterator implementations that may throw UnsupportedOperationException. As such, I'd say this approach is less safe than the first one. Depending on the implementations intended to be used, the first approach could be more suitable.

[Edwin Dalorzo]

This approach has many major disadvantages. First, every time you remove an element, the indexes are reorganized. Therefore, if you remove element 0, then the element 1 becomes the new element 0. If you are going to to this, at least do it backwards to avoid this problem. Second, not all List implementations offer direct access to the elements (as ArrayList does). In a LinkedList this would be tremendously inefficient because every time you issue an get(i) you have to visit all nodes until you reach i.

[Drake Clarris]

Never considered this as I typically just used it to remove a single item I was looking for. Good to know.

[Edwin Dalorzo]

In the first approach the disadvantage is that we have to iterate twice. We iterate in the foor-loop looking for an element, and once we find it, we ask to remove it from the original list, which would imply a second iteration work to look for this given item. This would support the claim that, at least in this case, iterator approach should be faster. We have to consider that only the structural space of the collection is the one being created, the objects inside the collections are not being copied. Both collections would keep references to the same objects. When GC happens we cannot tell!!!

[Bertie Wheen]

I'm late to the party, but surely in the if block code after Foo.remove(i); you should do i--;?

[Magno C]

Bravo! this is the definitive guide.

[Jack]

becouse it's bugged

[Wilhelm]

This is a perfect answer! Thank you.

[ifloop]

In your paragraph about JDK8 Streams you mention to removeAll(filtered). A shortcut for that would be removeIf(b -> b.getIsbn().equals(other))

[Alexander Mills]

What's the diff between Iterator and ListIterator?

[Matthew Read]

@EdwinDalorzo remove() on the original collection itself may also throw UnsupportedOperationException: docs.oracle.com/javase/7/docs/api/java/util/…. The Java container interfaces are, sadly, defined to be extremely unreliable (defeating the point of the interface, honestly). If you don't know the exact implementation that will be used at runtime, it's better to do things in an immutable way -- e.g., use the Java 8+ Streams API to filter the elements down and collect them into a new container, then entirely replace the old one with it.

[Akabelle]

Haven't considered removeIf, but it was the answer to my prayers. Thanks!

[mipasov]

Sometimes it is the only working solution.

[Uri Loya]

This does not answer the question of the OP, there is no iteration here

[Delark]

At first glance you may miss it, but the secret is to traverse the list backwards. This prevents that each removal, changes the index of future potential removals.

[Slaw]

@AlexanderMills and any others with the same question – ListIterator extends Iterator and provides more functionality: add and set, in addition to remove; iterate indices instead of elements; and ability to iterate in both directions.

[maxeh]

I would actually prefer to iterate from the beginning over the list, remove the item, and then decrement the counter. This has much better readability in my opinion. So just use: for (int i = 0; i < list.size(); i++) {...remove(i); i--;...}

[tarekahf]

Thanks a lot! This helped me to implement this solution here stackoverflow.com/questions/24182902/… .

[Fizz]

Actually the java docs on this are really confusing. "Iterators allow the caller to remove elements from the underlying collection during the iteration with well-defined semantics." remove() itself on the iterator may not throw that concurrent modification exception (scroll to remove in docs.oracle.com/javase/8/docs/api/java/util/Iterator.html) Also "The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method."

[judovana]

this would be not working if there are more items to remove, and if they are one riht behind other. To fix this, you need to i-- after the list.remove(i); or the backwards thing. Lookin to other replies ere, if yo need to remove more items after one condition, you have to stuck with improvrf this one

[éclairevoyant]

@UriLoya it's also likely that this question is an XY problem hence this answer.