Avoid Collection Modification During Iteration

We iterate over arrays, lists, or other data structures all the time. Most of the time, we only read from those data structures—for instance, when creating an invoice from a list of ordered items or searching for an item in a list by name. But you need to be careful when you modify the structure. Otherwise, you risk crashing your program.

This code describes a fairly simple iteration over a data structure: a List of supplies. If a Supply isContaminated(), the inventory system removes it from the List.

This code looks completely innocent, doesn’t it?

Although the code looks okay, it’ll crash reliably when at least one Supply in the inventory list is contaminated. Even worse, it’ll work fine until this happens the first time. And worse yet, it’ll work fine if all supplies are clean, making the bug hard to detect.

The problem is that we call supplies.remove(supply) while we’re inside a for loop that iterates over the supplies. In this situation, a standard implementation of the List interface, or indeed of other Collection interfaces such as Set or Queue, will throw a ConcurrentModificationException. We can’t simply modify a List while we iterate over it.

The name ConcurrentModificationException makes many people wonder about concurrency in their single-threaded application. That’s quite misleading, since no actual concurrency takes place here! Instead, we iterate over the Collection, and while we’re doing that, we modify that collection. Unfortunately, no compile-time check in Java saves us from this error.

So how can you do this properly without raising the ConcurrentModificationException?

In the straightforward solution to this problem, we would iterate the list in search of any contaminated supplies, and afterward, we would remove any previously found supplies. Think of a two-step approach: first iterate and then modify.

This would work, but it would require quite a few lines of code. And we would need to save the contaminated supplies in a temporary data structure during iteration. This would consume extra time and memory.

The solution we’ve depicted here uses another way of iteration: a while loop that relies on the Iterator of our supplies collection. The Iterator is our rescue. It acts like a pointer to an element in the list, starting with the first one. We can ask if any elements are left via hasNext(), get the next() element, and safely remove() the last element returned.

Although we can’t modify a List directly, the iterator is perfectly capable of doing this. Its job is to make sure that everything works during the iteration.

Technically, the for-each loop in the previous example also builds on such an iterator, but it hides this fact from the programmer. That’s nice, since it reduces the complexity of the code. But it also prevents us from using the remove() method of the iterator itself.

Some special List implementations like the CopyOnWriteArrayList can deal with modification during iteration. But such characteristics come at a price. Do you really want to copy the whole list each time you add or remove an element of it? Since Java 8, you can also use the new Collection.removeIf() method that makes use of lambdas. But be sure to read Chapter 8, ​Let Your Data Flow​ before you use that method!