fail fast iterator implementation

Question

There are similar questions but not exactly what I want to ask. I want to ask how Iterator checks for the modification.

This link says that its implementation is present in AbstractList class where an int variable modCount is defined that provides the number of times list size has been changed. This value is used in every next() call to check for any modifications in a function checkForComodification().

But I could not really understand it. If the value is checked only after every next call then if I do a remove followed by add in the same call, size won't change and modCount should not change as well. But removing and adding in the same loop iteration also throws exception.

Answer 1

If you look at the code for a Collection implementation, lets pick ArrayList; we have a modCount variable declared in AbstractList:

protected transient int modCount = 0;

And then in each and every modifying method (for example remove) for the ArrayList we have

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    //....

So the modCount is only ever incremented; it is never decremented.

In the Iterator we then have:

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

Where expectedModCount is a snapshot of the modCount taken at Iterator creation.

So if there is any modification to the underlying List while the same instance of an Iterator is in use then a ConcurrentModificationException will be thrown.

I suppose there is a corner case where if you carried out enough modifications then the int would overflow and return to it's original value again - this would be a rather large number or modifications however; 2³² to be precise.

Answer 2

modCount always increases when the list is modified (hence mod count) so it should also increase when there's a removal. Thus it would increase on both the remove and add call.

As Boris the Spider said there is the corner case that modCount overflows, you can see it by doing:

List<Integer> nums = new ArrayList<>();
for(int i = 0; i < 10; i++) nums.add(i);
for(int n : nums) {
    System.out.println(n);
    for(int i = -1; i < Integer.MAX_VALUE; i++) {
        nums.add(i);
        nums.remove(nums.size() - 1);
    }
}

Which will (slowly) print 0 through 9 without throwing any exception.