Closer Look into ArrayList Iterator

Background

Given an ArrayList of Integers from 0 (inclusive) to 10 (exclusive) with step size 1. We use a while-loop and an Iterator<Integer> to check if this ArrayList hasNext() element, before we remove() the current element.

Problem

The code below throws an IllegalStateException.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class UnderstandArrayListIterator {
    public static void main(String[] args) {
        List<Integer> a = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            a.add(i);
        }
        Iterator<Integer> iter = a.iterator();
        iter.next();
        while (iter.hasNext()) {
            iter.remove();
        }
    }
}

Discussion

After invoking remove(), lastRet is set to -1, so next time that this method is invoked, the condition lastRet < 0 in the if-block is satisfied, resulting in an IllegalStateException.

public void remove() {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();

    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

Things learnt

• ArrayList<E> uses a private inner class Itr implements Iterator<E>, in which
  • lastRet can be regarded as the “current element”
  • cursor is actually a key to retrive the next element returned by next().
  • expectedModCount records modCount when this iterator is instantiated.
• ArrayList<E> uses a transient class variable modCount to store the number of times that this ArrayList<E> has been structually modified (i.e. the number of times that this ArrayList<E>’s size has been changed) since this ArrayList<E> has been instantiated.
  • a transient class member doesn’t reflect the state of an object, so it’s not included in the serialized object. For example, here’re two ways to get a same state while clearing an ArrayList<E> of multiple objects:
    • clear() all elements, leading to an increment of modCount by 1.
    • remove(int index) / remove(Object o) elements one-by-one, leading to a total increment of modCount that equals to the ArrayList<E>’s size.
  • clone() resets modCount to 0 since the cloned list has another return type Object, i.e. another object.
  • Java Point provides an example of concurrent modification that has a list ({1, 2, 3, 4, 5}) and its iterator. Inside a while(it.hasNext())-loop,
    1. each value in list is compared to 3.
    2. when a matching occurs (i.e. it.next() returned 3), remove 3 from the list by list.remove(3), for the purpose of reproducing a ConcurrentModificationException, so that modCount increments by 1. Since this instruction doesn’t involve it, and modCount is of primitive type, expectedModCount doesn’t change.
    3. a ConcurrentModificationException should be produced, since such deletion introduces a left-shifting of the “tail” (i.e. all elements that comes after the deleted element. ({4, 5})), it’s field cursor (that stores the index of the element 4 next to the deleted element 3) is greater than what we expect by 1. That’s not a usual use case, so such exception is thrown to stop the process from running.
    4. in the next iteration, the next() method is invoked. In this method, checkForComodification() is invoked. This name of checkForComodification is self-explanatory. Inside the final void method checkForComodification(), it does one simple thing: check if (modCount != expectedModCount), and throw new ConcurrentModificationException() if the actually modification count is different from what we expected. In this example, the condition in this if-block is verified for the reason explained in point no. 2, so a ConcurrentModificationException is thrown.
    5. If we’re modifying this list normally (through it.remove()), we shouldn’t get this error because in the try-block of the inner class method Itr#remove(), there’s a value assignment expectedModCount = modCount.
    6. remarks for this example: IMHO, using alphabets instead of digits for the list’s entries is much less confusing, since my proposed entry type char can’t be confused with the index’s type int.
• Collection<E>#remove(Object o) accepts whatever object, but it throws
  • ClassCastException if o can’t be casted into type E.
  • NullPointerException if o is null and this collection doesn’t accept null entry value.
• ArrayList<E>#clone() returns a shallow copy of this ArrayList<E>, i.e. a different instace of ArrayList<E> in which every element is copied by reference.