ConcurrentModificationException

You cannot edit a collection while looping over it.

This is a truism of many programming languages, and this problem is called Iterator Invalidation.

For example, consider the following python program:

xs = ['A', 'b', 'c', 'D', 'e', 'F']

for x in xs:
    if x.islower():
        xs.remove(x)

print(xs)

Any guesses as to what this prints?

That's right. It prints just the upper-case strings:

xs = ['A', 'c', 'D', 'F']

Wait a minute. What's that 'c' doing in there? It did the wrong thing.

In Java, the equivalent code throws an error, a ConcurrentModificationException.

List<Character> letters = new ArrayList<>(List.of('A', 'b', 'c', 'D', 'e', 'F'));

for (Character c : letters) {
    if (c.isLowerCase()) {
        letters.remove(c);
    }
}

List invariant: no empty indices

Lists don't have blank spaces.

If you take a list, e.g., ['A', 'b', 'c', 'D', 'e', 'F']:

0	1	2	3	4	5
A	b	c	D	e	F

And ask it to remove the index 1 element, you expect to get ['A', 'c', 'D', 'e', 'F'].

The size gets smaller. The elements after the 'b' slide to the left.

Iterator Invalidation

The property where lists never have blanks and always inhabit the lowest possible indices wreaks havoc if you're modifying a list and looping over it at the same time.

So... imagine you're looping through a list, using an index.

You stop on that lower-case 'b', index=1:

0	1	2	3	4	5
A	b	c	D	e	F

You issue the call to remove. Everything slides down; your index still is at 1.

0	1	2	3	4
A	c	D	e	F

... Now you're pointing at 'c', but you don't notice. You go around the loop again, incrementing your index...

0	1	2	3	4
A	c	D	e	F

'D' is not lowercase, so you move on. The 'c' slid to the left, into your 'blind spot' and you'll never end up deleting it.

Fixing This Problem in Java:

Solution 1: Copy the List

List<Character> letters = new ArrayList<>(List.of('A', 'b', 'c', 'D', 'e', 'F'));

for (Character c : new ArrayList<>(letters)) {
    if (c.isLowerCase()) {
        letters.remove(c);
    }
}

Now you're looping over a temporary arraylist, but deleting from the original. Solved!

Solution 2: Create a toDelete List

List<Character> letters = new ArrayList<>(List.of('A', 'b', 'c', 'D', 'e', 'F'));

List<Character> toDelete = new ArrayList<>();
for (Character c : letters) {
    if (c.isLowerCase()) {
        toDelete.add(c);
    }
}

// shorter: letters.removeAll(toDelete);
for (Character d : toDelete) {
    letters.remove(d);
}

Then you're looping over toDelete while modifying letters so you're safe. Note you can use removeAll to save yourself writing this second for-loop.

Solution 3: Re-frame the problem as a 'filter'

Rather than delete from a list; just make a new list containing what you want to keep.

List<Character> letters = new ArrayList<>(List.of('A', 'b', 'c', 'D', 'e', 'F'));

List<Character> uppercase = new ArrayList<>();
// Loop backwards to avoid concurrent modification:
for (Character c : letters) {
    if (c.isUpperCase()) {
        uppercase.add(c);
    }
}
// now use uppercase instead!

This requires that you're OK making a new list, but most of these solutions do that one way or another.

Solution 4: Loop backwards

To deal with the fact that things slide to the left, you can also loop to the left. (Simulate it in your head to prove to yourself this is OK.)

List<Character> letters = new ArrayList<>(List.of('A', 'b', 'c', 'D', 'e', 'F'));

// Loop backwards to avoid concurrent modification:
for (int i=letters.size()-1; i>=0; i--) {
    Character c = letters.get(i);
    if (c.isLowerCase()) {
        // we can delete by position now:
        letters.remove(i);
    }
}

I tend to mess up looping backwards (so easy to have an off-by-one error) so this is my least favorite solution.