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!