Iterator remove throws ConcurrentException

Question

Was trying to implement in-place purge on a list.

        Iterator<Integer> itr = ls.iterator();
        for (Integer x : ls) {
            int count = 0;
            while(itr.hasNext()){
                if (itr.next().equals(x)) {
                    count++;
                    if (count > 1) {
                        itr.remove();
                    }
                }
            }
        }

Exception in thread "main" java.util.ConcurrentModificationException

        Iterator<Integer> iterator = numbers.iterator();
        while (iterator.hasNext()) {
            if (iterator.next() == 1) {
                iterator.remove(); // Doesn't throw exception
            }
        }

However, with just one loop thought it doesn't. Why ?

what is the reasoning for this behavior

Answer 1

You have two iterators over ls here:

• The one created explicitly via ls.iterator();
• The one created implicitly via for (Integer x : ls).

If you call remove() on the first iterator, it invalidates the second iterator, meaning any invocations of next() on the second iterator cause (or are prone to causing) a ConcurrentModificationException to be thrown.

---

A possible way to do an in-place deduplication might be like this:

int dst = 0;
for (Integer x : ls) {
  if (!ls.subList(0, dst).contains(x)) {
    ls.set(dst++, x);
  }
}
ls.subList(dst, ls.size()).clear();

This shifts elements that haven't been seen before to the left in the array; and then removes all other elements from the array afterwards.

Changing the list in the loop doesn't result in a ConcurrentModificationException because there is no structural modification to the list.

Answer 2

Here is another possibility that avoids a concurrent mod exception. To remove duplicates use a set.

 List<String> list = new ArrayList<>(List.of("A","B","C","D","A","B","B","E"));
 Set<String> set = new LinkedHashSet<>();
 set.addAll(list);
 System.out.println(set);

prints

[A, B, C, D, E]

Note: Any set could be used. A linked hash set preserves insertion order.

Answer 3

In order to look in to this problem we need to study how the Java enhanced for loop works internally.

Java enhanced for loop is internally using a Fail Fast Iterator which uses an internal flag named modCount (This updats each time when ever the collection is modified) to track the structure of collection manipulated or not. If there is any change then it's throwing ConcurrentModificationException.

Please see the following synonym code for the enhanced for loop.

 List<Integer> ls = Arrays.asList(1,2,3);

 for (Integer x : ls) {

 }

Synonymous code with internal code structure

for (Iterator<Integer> itr = ls.iterator(); itr.hasNext();) {
   Integer x = itr.next(); 
}

Because of the above code structure, the enhanced for loop is not allowing to remove elements while iterating.

Even though there is no explicit reference to the for iterator to call the remove() method, if remove() method is called on List then ConcurrentModificationException is firing.

Finally, the reason for ConcurrentModificationException should be you are calling remove() method on the iterator itr, which works on the same list ls while invoking enhanced for loop related to same list ls.

Answer 4

There is one hiccup I ran into implementing this algo

purgeInplace(Arrays.asList(1, 2, 3, 1))

throws

Exception in thread "main" java.lang.UnsupportedOperationException
        at java.base/java.util.AbstractList.remove(AbstractList.java:169)
        at java.base/java.util.AbstractList$Itr.remove(AbstractList.java:389)
        at java.base/java.util.AbstractList.removeRange(AbstractList.java:600)
        at java.base/java.util.AbstractList$SubList.removeRange(AbstractList.java:813)     
        at java.base/java.util.AbstractList.clear(AbstractList.java:245)
        at PurgeUtil.purgeInplace(PurgeUtil.java:25)
        at PurgeUtil.main(PurgeUtil.java:15)

However, purgeInplace(new ArrayList<>(Arrays.asList(1, 2, 3, 1)));

works fine.

ps. Couldn't put this under a comment because of word limit.