Saturday, May 10, 2014

Java ArrayList vs CopyOnWriteArrayList

ArrayList:

ArrayList is a basic implementation of List interface in Collection framework.It extends AbstractList. ArrayList supports dynamic array that can grow as needed.

Some of the important methods in ArrayList are

void add(int index,Object element):add the element at the specified index.
void add(Object element): Add the element at the end of the list.
void  clear(): clears the list when called on the list.
Object remove(int index): Remove the element at the specified location

We need an iterator to iterate over the list. ArrayList iterator is fail-fast by design.That means as soon as the underlying data structure changes after creating iterator it will throw java.util.ConcurrentModificationException.


Internally when we create an array list, it will maintains a modCount variable which will keep track of the modification count and every time we use add, remove or trimToSize method, it increments. expectedModCount is the iterator variable that is initialized when we create iterator with same value as modCount. This explains why we don’t get exception if we use set method to replace any existing element.

So basically iterator throws ConcurrentModificationException if list size is changed.

Let's run the program to see 


 package misc;  
 import java.util.ArrayList;  
 import java.util.Iterator;  
 import java.util.List;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new ArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

Output:

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at misc.CopyOnArrayListExample.main(CopyOnArrayListExample.java:30)

As you can see, ArrayList iterator doesn't allow concurrent modification when we iterating.If we need to do concurrent modification then we need  CopyOnWriteArrayList.

Lets see CopyOnWriteArrayList in action.


package misc;  
 import java.util.Iterator;  
 import java.util.List;  
 import java.util.concurrent.CopyOnWriteArrayList;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new CopyOnWriteArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

In above code, we just changed the class definition from ArrayList to CopyOnWriteArrayList and see the output below.

James Gosling
Brendan Eich
Rod Johnson
Gavin King
Un Known

As you can see, the above code doesn't throw any exception as this one is thread safe variant of ArrayList.

Few things about CopyOnWriteArrayList from official documentation

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

All elements are permitted, including null.

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.

Thanks for visiting my blog!!!!!!!!