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.

Solution 1

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.}

Solution 2

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.

Solution 3

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.

Comments

[Andrii Plotnikov]

This one actually is more proper answer

[AnirbanDebnath]

This is best explanation.

[Saddam Pojee]

Good explanation. This should be the correct answer.

[Stephen C]

It is an explanation for the implementation of the behavior (in various collection classes). But the reason for the behavior is that the Iterator class is designed to work this way ... and specified to work this way. The design / specification give rise to the implementation, not the other way around.

[Stuart Marks]

@StephenC In this case the design and specification were informed by implementation considerations. Sure, Iterator is designed and specified to work the way it does... but why? The answer is that it's a tradeoff among predictability, reliability, ease of implementation, and ease of use. It's easy to contemplate a specification with stronger guarantees, but that would impose burdensome requirements on implementations. I could explain further, but this comment is getting long. If you'd like additional explanation, feel free to ask a question. :-)