Unspecified behavior of the Java Iterator

In this article we will take a look at how the behavior of the Iterator produces some surprising results if not used in the right away.

In my previous article, we saw different ways of  removing elements from an ArrayList. When we used the remove(Object o) method from the ArrayList while we traverse through the ArrayList, we get a ConcurrentModificationException. But is this always the case ?

Well, let’s consider the same example of removing a person below the age of 18 from an ArrayList but with a different data set.

Most of the code remains the same, the only thing that has changed is the data. Notice the Person data on the 2nd last and last elements in the ArrayList.

persons.add(new Person("Kimmo", 17, Gender.MALE, Citizenship.FINLAND));
persons.add(new Person("Simo", 17, Gender.MALE, Citizenship.FINLAND));

Well, anyways, we should get a ConcurrentModificationException! Right ?

On running this the output :

[Rahul, Sally, Ben, Wayne, ShaneYoung, Simo]

Shocked ? No exception ! Not just that , Simo should have been filtered. Well, lucky Simo! He can still have beer even though he is 17.

So what is happening  ?  Why is an exception not thrown and why is the last element returned ?

The 2nd last element satisfies the filtering criteria , it gets deleted. When it gets deleted, the size of the ArrayList is reduced by 1. But, the combination of Iterating and calling remove(Object o) makes the Iterator to behave in a weird way.  When remove(Object o) is called, it makes a call to the fastRemove method which reduces the size of the list. Then there is a call to the hasNext() on the iterator to check if there are more elements to to traversed. The hasNext() looks as follows:

public boolean hasNext() {
    return cursor != size;
 }

The cursor is an index that points to the index of the next element that will be processed. It starts from 0. In our case when we delete the 2nd last element, the cursor value is 6.

Before deleting: (size =7 , cursor =6 at Simo)

Rahul
21
Sally
21
Ben
35
Wayne
30
ShaneYoung
30
Kimmo
17
Simo
  17

After deleting: (size =6 , cursor = 6 at Simo)

Rahul
21
Sally
21
Ben
35
Wayne
30
ShaneYoung
30
Simo
17

Original value of size in our list is 7. When 2nd last element(Kimmo) is deleted, size =6 , cursor = 6. The Iterator thinks all the elements have been visited. So after deleting, when hasNext() is called ( remember that an enhanced for loop still means that the Iterator is used for moving around), the above condition returns false and hence the next() is not called. The last element is completely skipped and included in the output ! Since the hasNext returns false, next() is not called and the exception is not thrown. It is the call to next() which checks for concurrent modification but it is never called.

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

The Javadoc for Iterator remove method clearly states that the behavior of the iterator is unspecified if the underlying collection is modified while the iteration is in progress in any other way than by calling Iterator remove(). So the above behavior is pretty much unspecified but can catch you by surprise.

Conclusion

Read the Javadocs carefully!  I know you are religiously going to do that 🙂 !

If you are still using Java 7 or any version below that, don’t by pass the gate keeper, “The Iterator “, when simultaneously looping and deleting elements from an ArrayList. Use the remove() method from the Iterator.

Removing elements from a Java ArrayList

In this article we are going to look at the different ways of removing elements from a Java ArrayList. We will be looking at why some ways work, some might appear to work and some don’t. Finally we will look at the recommended way to remove elements from an ArrayList.

Let us assume that we have a list of Persons with name, age , gender and citizenship. Drinking below the legal age is considered a crime in most places. Let us say we want to remove these persons from the list assuming the legal age for drinking is > 18.

First Attempt – The Exceptional way

We can remove the desired elements from an ArrayList using the code below.

Take a look at the removeIllegalUsingEnhancedForLoop  method which uses the enhanced for loop. The initialize method adds some data to the ArrayList. Well, the code looks quite straightforward. But on running this, we get a ConcurrentModificationException.

Exception in thread "main" java.util.ConcurrentModificationException
 at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
 at java.util.ArrayList$Itr.next(ArrayList.java:851)
 at blog.RemoveItems.removeIllegalUsingEnhancedForLoop(RemoveItems.java:52)
 at blog.RemoveItems.main(RemoveItems.java:27)

The moment you see the word Concurrent , you are thinking, why I am getting this exception, I am not using threads ! Note that while iterating using the enhanced for loop we are also trying to remove elements, which means we are modifying the structure of the list while we are iterating. Keep in mind that we are using the <arrayList>.remove(Object o). 

But from a technical perspective, what is happening behind the scenes?

Even though we are using an enhanced for loop, there is an Iterator involved behind the scenes. The Iterator is an interface. ArrayList implements the Iterator interface via a private inner class, Itr. When we use the enhanced for loop, there is a call to a method iterator() in the ArrayList when the for loop is going to be executed.

public Iterator<E> iterator() {
 return new Itr();
 }

This Itr is the one that maintains the state of the ArrayList. It does this using 2 variables, one is the modCount and the other one is the expectedModCount. modCount is an instance variable which keeps track of the number of times the ArrayList is modified. So far we only added elements, 6 to be precise, so the modCount is 6. The Itr class maintains the expectedModCount. Since this Itr class implements Iterator interface, it provides implementation for next(), hasNext(), remove().  Note that the remove method here does not take any arguments.

When we say persons.remove(p), the ArrayList remove method which takes an object as a parameter is called and not the Itr remove(). This remove(Object o) method makes a call to fastRemove() which does increase the value of the modCount but does not touch the expectedModCount. When the element is deleted  in our case, the modCount becomes 7 but the expectedModCount is still 6. Even if you use an enhanced for loop, the elements in the ArrayList are iterated using the next, hasNext method. The next method is called as the iteration moves ahead. The next method has this piece of code :

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

The method next checks for modification by evaluating if modCount and expectedModCount are not equal. Since the expectedModCount has not been touched in the remove(Object o) of the ArrayList, we get this ConcurrentModificationException. In short, the ArrayList was changed without use of the Iterator.remove. It is the Iterator which maintains the internal state. We removed the element using <arrayList>.remove(Object o) leaving the Iterator puzzled, so the Iterator complains about ConcurrentModificationException. It complains that –  “Hey, you did not remove elements through me, I am the gate keeper and since you did not get your gate pass, I am going to throw an exception”.

So if this is not the right way of removing elements,  can we remove elements using an Iterator directly ?

Second Attempt – The Heavy duty Iterator way of removing elements

The Iterator has a remove method.We need to use this remove method. This is how it is done :

This works fine and we do not get any Exceptions. We are making use of personIterator.remove().

Why does this work ?

Itr inner class in the ArrayList implements Iterator interface.  It also maintains the correct state by increamenting modCount but also assigning expectedModCount to modCount. When we call remove() on the Iterator, not only does it increase the value of the modCount by 1 but it also does the following :

expectedModCount = modCount;

So the call to next() as shown above calls :

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

This does not throw a exception as they are equal now. You got your gate pass and now the guardian of the ArrayList, the gatekeeper, the Iterator, is happy !

So obviously we must use the Iterator to remove the elements from an ArrayList while we are iterating. Well, true, if you are still stuck with Java 7. This brings us to the 3rd way of implementing removal.

Third attempt – Java 8 cute way of removing elements from an ArrayList

Did you stare at the code a couple of times ? Have I missed out on showing you some code ? That is the code , yes it is ! Trust me!  You don’t ? Well, then go ahead and try it out.

The removeIf is a method added in Java 8. It has been added and has an implementation in the Collection interface. Yes, you read that right, Collection interface. It is a default method.

default boolean removeIf(Predicate<? super E> filter) {

}

This method is however overridden in the ArrayList class. It takes a Predicate which is a Functional interface. If you refer to the removeIllegalUsingJava8 method, we are passing a Lambda, person -> person.getAge() < 18. This is passed to the Predicate interface and then in the removeIf method, the test method is called. If the condition is satisfised, the element is removed. Finally the modCount is incremented to indicate that the ArrayList has gone through a modification.

So should we use this method now because it looks cute and concise ? Well that is a start. The code is short and concise, it clearly tells us it’s intention – Remove an element that satisfies this condition.

Not convinced about the cuteness – There is more to it !

The removeIf method is also more performant. What ? Cute and Efficient ? Hard to believe ? Well, the removeIf method removes and manages the elements in the ArrayList in a different was as compared to the Iterator way of removing and adjusting the elements in the ArrayList. The remove method using an Iterator uses System.arrayCopy and shifts the elements each time an element is removed from the list. This can considered as O(n^2).

The removeIf method take a different approach. It uses a BitSet class and does not use a System.arrayCopy. It creates a BitSet to maintain the index of the elements that need to be removed. It finally shifts the elements once rather than shifting them each time. So it also performs better than the Iterator remove and the performance is O(n).

Conclusion

The Java 8 removeIf way of implementing removal is not only cute but performs better. Beauty with Brains ? That is a lethal combination, I urge you to start using it!