Why iterator.remove does not throw ConcurrentModificationException

Question

What does iterator.remove() do differently from list.remove(), so that iterator does not throw an exception and list.remove() does throw one? In the end, both are modifying the collection size.

Please ignore multi-threading here. I am just talking about a for-each loop and an iterator loop. As far as I know, a for-each loop creates an iterator only internally.

I am confused.

Answer 1

Answering this question with few additional low level details:

ConcurrentModificationException is thrown at next call to next() method during iteration.

So its not remove() method of collection which throws this exception, but its next() method of iterator implementation.

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1013)
    at java.base/java.util.ArrayList$Itr.next(ArrayList.java:967)
    at Collection.IteratorDemo.main(IteratorDemo.java:16)

you can check line number 3 in above error log.

  List<Integer> nums = new ArrayList<>();
     nums.add(1);
     nums.add(2);
     for(int i : nums){
        nums.remove(1);
        System.out.println(i);
 }

How does this next() method know if collection is modified?

By checking a variable, AbstractList

 protected transient int modCount = 0;

This variable maintains structural changes to collection by incrementing and decrementing value in add/remove call to collection. This is how fail-fast iterator are implemented by collections.

Answer 2

ConcurrentModificationException is not thrown by Iterator.remove() because that is the permitted way to modify an collection while iterating. This is what the javadoc for Iterator says:

Removes from the underlying collection the last element returned by this iterator (optional operation). This method can be called only once per call to next(). 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.

If you change the collection being iterated any other way, then you are liable to get an exception, depending on the implementation of iterator, and the collection (or whatever) that you are iterating. (Some collection classes won't give you a ConcurrentModificationException: check the respective javadocs to see how they specify the behavior of their iterators)

You are also liable to get an exception if you have two iterators on the same collection, and you remove via one of them.

---

What iterator.remove does different from list.remove that iterator does not throw exception while list.remove does throw?

Reason #1. If you had a non-concurrent collection being updated simultaneously from two places on the same call stack, the behavior would break the design invariant for the iteration¹. An iteration of a non-concurrent collection is guaranteed to see all of the elements in the collection exactly once. (By contrast, with concurrent collections these guarantees are relaxed.)

Reason #2. Non-concurrent collection types are not implemented to be thread-safe. Therefore, you could have race conditions and memory anomalies if the collection and iterator are used to update the collection by different threads. This is not strong reason because you will have these problems anyway. However, having the updates happening in two different ways makes the problem worse.

---

I am just talking about for-each loop and iterator loop. As far as I know for-each loop internally create iterator only.

That is correct. A for-each loop is really just syntactic sugar for a while loop using an iterator.

On the other hand, if you use a loop like this:

    for (int i = 0; i < list.size(); i++) {
        if (...) {
            list.remove(i);
        }
    }

you won't get ConcurrentModificationException, but you will need to adjust the index variable for the elements that you delete, and updates by another thread are liable to cause you to skip elements or visit them more than once².

---

^{1 - To achieve "exactly once" iteration behavior, when you remove an element via the collection object, the iterator data structure would need to be updated to keep it in step with what has happened to the collection. This is not possible in the current implementations because they don't keep links to the outstanding iterators. And if they did, they would need to use Reference objects or risk memory leaks.}

^{2 - Or even get an IndexOutOfBoundsException. And if the collection is not concurrent / properly synchronized, you can get worse problems.}

Answer 3

I think you mean, if you're iterating a list, why does list.remove() cause a ConcurrentModificationException to be thrown whereas iterator.remove() does not?

Consider this example:

    List<String> list = new ArrayList<>(Arrays.asList("a", "b", "c", "d"));

    for (Iterator<String> iter = list.iterator(); iter.hasNext(); ) {
        if (iter.next().equals("b")) {
            // iter.remove();    // #1
            // list.remove("b"); // #2
        }
    }

If you uncomment line #1, it will work fine. If you uncomment line #2 (but leave #1 commented) then it will cause the subsequent call to iter.next() to throw ConcurrentModificationException.

The reason is that the iterator is a separate object that has some references to the internal state of the underlying list. If you modify the list while the iterator is in operation, it could cause the iterator to behave badly, e.g. by skipping elements, repeating elements, indexing off the end of the array, etc. It attempts to detect such modifications and so it throws ConcurrentModificationException if it does.

Removing elements through the iterator works and does not cause exceptions, because this updates the underlying list and the iterator's state that refers to the internals of the list, so everything can stay consistent.

However, there is nothing special about iterator.remove() that makes it work in all cases. If there are multiple iterators iterating over the same list, modifications made by one will cause problems for the others. Consider:

    Iterator<String> i1 = list.iterator();
    Iterator<String> i2 = list.iterator();
    i1.remove();
    i2.remove();

We now have two iterators pointing into the same list. If we modify the list using one of them, it disrupts the operation of the second, so the call to i2.remove() will result in ConcurrentModificationException.

Answer 4

public class ArrayListExceptionTest {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("a");
        list1.add("b");
        list1.add("c");
        Iterator<String> it1 = list1.iterator();
        ArrayList<String> list2 = new ArrayList<String>();
        list2.add("a");
        try {

            while (it1.hasNext()) {
                list1.add(it1.next());
            }
        } catch (ConcurrentModificationException e) {
            e.printStackTrace();
        }
        it1 = list1.iterator();
        while (it1.hasNext()) {
            System.out.println(it1.next());
        }
        it1 = list1.iterator();
        try {
            while (it1.hasNext()) {
                if (it1.next().equals("a"))
                    list1.retainAll(list2);
            }

        } catch (ConcurrentModificationException e) {
            e.printStackTrace();
        }
        it1 = list1.iterator();
        while (it1.hasNext()) {
            System.out.println(it1.next());
        }
        it1 = list1.iterator();
        Iterator<String> it2 = list1.iterator();
        it1.remove();
        it2.remove();
    }
}

You can see the above 3 cases

case 1: Modification made by adding the element, hence when next() function is used it resulted in ConcurrentModificationException.

case 2: Modification made by using the retain(), hence when next() function is used it resulted in ConcurrentModificationException.

case 3: Will throw java.lang.IllegalStateException not ConcurrentModificationException.

Output:

a
b
c
a

a
a

    java.util.ConcurrentModificationException
        at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
        at java.util.ArrayList$Itr.next(ArrayList.java:859)
        at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:21)
    java.util.ConcurrentModificationException
        at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
        at java.util.ArrayList$Itr.next(ArrayList.java:859)
        at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:37)
    Exception in thread "main" java.lang.IllegalStateException
        at java.util.ArrayList$Itr.remove(ArrayList.java:872)
        at com.rms.iteratortest.ArrayListExceptionTest.main(ArrayListExceptionTest.java:55)

Answer 5

Here is an example how things could go wrong if collection iterators didn't check for modifications of the underlying collection. This is how ArrayLists's iterator is implemented:

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such

    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size) throw new NoSuchElementException();
        // ...
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        // ...
        ArrayList.this.remove(lastRet);
        // ...
        cursor = lastRet;
        lastRet = -1;
    }

Let's look at an example:

List list = new ArrayList(Arrays.asList(1, 2, 3, 4));
Iterator it = list.iterator();
Integer item = it.next();

We remove the first element

list.remove(0);

If we want to call it.remove() now, the iterator would remove number 2 because that's what field lastRet points to now.

if (item == 1) {
   it.remove(); // list contains 3, 4
}

This would be incorrect behavior! The contract of the iterator states that remove() deletes the last element returned by next() but it couldn't hold it's contract in the presence of concurrent modifications. Therefore it chooses to be on the safe side and throw an exception.

The situation may be even more complex for other collections. If you modify a HashMap, it may grow or shrink as needed. At that time, elements would fall to different buckets and an iterator keeping pointer to a bucket before rehashing would be completely lost.

Notice that iterator.remove() doesn't throw an exception by itself because it is able to update both the internal state of itself and the collection. Calling remove() on two iterators of the same instance collection would throw, however, because it would leave one of the iterators in an inconsistent state.

Answer 6

Because it is the iterator that throws the exception. If you call List.remove() it doesn't know about the removal, only that something has changed under its feet. If you call Iterator.remove() it knows the current element was removed and what to do about it.