ArrayList features every Java developer must know

Hello Friends,

In this tutorial ,we will discuss following features of one of the very commonly and vastly used collection ArrayList.

1. What is ArrayList

2. What is the capacity of ArrayList.

3. How ArrayList capacity grows dynamically.

4. What is difference between capacity and size of ArrayList.

5. Ordered nature of ArrayList.

6. Duplicate values are allowed in ArrayList.

7. Null values are allowed in ArrayList.

8. ArrayList is not synchronized

1. What is ArrayList? 

ArrayList is one of the collection provided by Collection framework of Java represented by java.util.ArrayList.

We can think of ArrayList as dynamically growing array.

If we create array, we need to give size of the array on instantiation as below: 

Integer[] arr = new Integer[10];

Which means that we can add maximum up to 10 elements in this array like below

arr[0] = 1;
arr[1] = 2;
.
.
arr[9] =9;

Now if we will try to add 11th element in this array as below

arr[10] = 10;

This will throw exception at run time ,something like

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10

Which shows that once we have created/instantiated an array of particular size,we can add maximum number of elements equal to the defined size of array only and not more than that.

But this is not the case with ArrayList. You can instantiate an ArrayList as below and still can  add n number of elements in it.

List<String> list = new ArrayList<String>();

To understand how it happens lets see first, capacity of ArrayList.

2. What is Capacity of ArrayList

When we instantiate an ArrayList,it is instantiated with initial capacity of 10,which means an array of size 10 is created to store 10 elements initially or in other words memory for 10 elements is allocated.
Below are the constructors of the java.util.ArrayList from source code of java.util.ArrayList,

Constructor 1 :

   /**
     * Constructs an empty list with the specified initial capacity. 
     * 
     * @param  initialCapacity  the initial capacity of the list 
     * @throws IllegalArgumentException if the specified initial capacity 
     *         is negative 
     */ 
    public ArrayList(int initialCapacity) { 
        super(); 
        if (initialCapacity < 0) 
            throw new IllegalArgumentException("Illegal Capacity: "+ 
                                               initialCapacity); 
        this.elementData = new Object[initialCapacity]; 
    }

Constructor 2 :

 /**
  * Constructs an empty list with an initial capacity of ten.
  */
  public ArrayList() {
      this(10);
  }

Instantiating way 1 :

So if we create instance of ArrayList class as below :

List<String> list = new ArrayList<String>();

It will call Constructor 2,which will call constructor 1 with parameter 10.
In the first constructor below line is actually instantiating an array elementData of size 10.

this.elementData = new Object[initialCapacity];

Here elementData is an instance variable of the java.util.ArrayList class and
is declared as below :

/**
  * The array buffer into which the elements of the ArrayList are stored.
  * The capacity of the ArrayList is the length of this array buffer.
 */
private transient Object[] elementData;

Instantiating way 2 :

If we will instantiate ArrayList like below

List<String> list = new ArrayList<String>(-1);

It will call Constructor 1 with parameter -1.Now as in Constructor 1,it is checking that initialCapacity should not be less than zero and if so, then
throw IllegalArgumentException explicitly, hence you will get following exception :

java.lang.IllegalArgumentException: Illegal Capacity: -1
 at java.util.ArrayList.<init>(ArrayList.java:110)

However ,If we want to instantiate an ArrayList with initial capacity greater than 10,as we might be already aware in starting that our ArrayList is going to take large amount of data, then we can do like below :

List<String> list = new ArrayList<String>(30);

Above line will call constructor 1 and will instantiate an array with size of 30. Actually ArrayList can contain any number of items as long there is enough memory for it and when doing large initial insertions we can tell ArrayList to allocate a larger memory space to begin with to avoid wasting CPU cycles when it tries to allocate more space for the next item.

3. How ArrayList capacity grows dynamically ?

That is interesting question actually and answer is equally interesting :)
So say we created an ArrayList(Intial capacity 10) and added 10 elements as below :

List<String> list = new ArrayList<String>();
list.add("1");

After above line, 
Size of ArrayList list : 1
Capacity of ArrayList list : 10

list.add("2");

After above line, 
Size of ArrayList list : 2
Capacity of ArrayList list : 10

list.add("3");

After above line, 
Size of ArrayList list : 3
Capacity of ArrayList list : 10

.

.

.

list.add("10");

After above line, 
Size of ArrayList list : 10
Capacity of ArrayList list : 10
So far so good,as intial capacity of ArrayList was 10,we added 10 elements in it.Now lets add 11th element in it.

list.add("11");

After above line, 
Size of ArrayList list : 11
Capacity of ArrayList list : 15
Let us see how capacity increased from 10 to 15.

Below is the source code of add method which gets executed on call to add method.As you can see from within add method call is made to ensureCapacityInternal method with parameter "size+1".Here size is the size of the list i.e number of elements actually contained in the list.so when we added 11th element in the list ,parameter passed to ensureCapacityInternal will be 11(10 +1).

   /**
     * Appends the specified element to the end of this list. 
     * 
     * @param e element to be appended to this list 
     * @return <tt>true</tt> (as specified by {@link Collection#add}) 
     */ 
    public boolean add(E e) { 
        ensureCapacityInternal(size + 1);  // Increments modCount!! 
        elementData[size++] = e; 
        return true; 
    } 

    private void ensureCapacityInternal(int minCapacity) { 
        modCount++; 
        // overflow-conscious code 
        if (minCapacity - elementData.length > 0) 
            grow(minCapacity); 
    } 

   /**
     * Increases the capacity to ensure that it can hold at least the 
     * number of elements specified by the minimum capacity argument. 
     * 
     * @param minCapacity the desired minimum capacity 
     */ 
    private void grow(int minCapacity) { 
        // overflow-conscious code 
        int oldCapacity = elementData.length; 
        int newCapacity = oldCapacity + (oldCapacity >> 1); 
        if (newCapacity - minCapacity < 0) 
            newCapacity = minCapacity; 
        if (newCapacity - MAX_ARRAY_SIZE > 0) 
            newCapacity = hugeCapacity(minCapacity); 
        // minCapacity is usually close to size, so this is a win: 
        elementData = Arrays.copyOf(elementData, newCapacity); 
    }

Now lets see what ensureCapacityInternal method is doing.It will call grow method if
following condition is true

if (minCapacity - elementData.length > 0)

In our case 
minCapacity = 11
elementData.length = 10
so minCapacity - elementData.length = 11-10 =1 which is greater  than zero,hence condition will be true on addition of 11th element and grow method will be called.
Now lets explore grow method

int oldCapacity = elementData.length;

In our case
oldCapacity  = 10

int newCapacity = oldCapacity + (oldCapacity >> 1); 

In our case
newCapacity =10 + 0.5*10 =15
Here >> is right shift operator which reduces a number to its half

if (newCapacity - minCapacity < 0) 

In our case
newCapacity - minCapacity = 15-11 =4 which is not less than zero hence next line inside if statement will not be called.

newCapacity = minCapacity; 

if (newCapacity - MAX_ARRAY_SIZE > 0)

In our case

newCapacity - MAX_ARRAY_SIZE  = 15 - 2147483639 = -2147483624,which is not greater than zero,hence next line within If statement will not be executed.

newCapacity = hugeCapacity(minCapacity); 

Note : MAX_ARRAY_SIZE is defined in ArrayList class as below

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

Next control will reach on below line and this line will create new Array object with capacity 15 using static copyOf method of Arrays class.It will copy the elements of old array to this new array and elementData will start referring to this new Array.Hence there is increase in capacity from 10 to 15 now.

elementData = Arrays.copyOf(elementData, newCapacity); 

Next time when 16th element will be added,new size will be calculated as below

15+0.5*15 = 22

and so on.

Note : Differenr JDK implementations can have different logic the way capacity increases.I am using open JDK 7 implementation here.

So we understood from above discussion that how capacity of ArrayList increases.One thing we need to understand here also is difference between capacity and size of Arraylist,which is described as below.

4. Difference between Size and Capacity of ArrayList

As we discussed above, ArrayList is actually backed by an array ,i.e. elements of ArrayList are actually stored in array. The capacity of ArrayList is the size of this array which stores elements of ArrayList. The capacity of ArrayList at any time will be at least equal to the size of the ArrayList, which in other words means that capacity of ArrayList can never ever be less than size of the ArrayList. This is due to the reason that whenever it's size reaches maxmimum capacity,capacity is increased by 0.5*old Capacity.
Size of ArrayList is the actual number of elements contained within an ArrayList.
Lets see capacity and size of ArrayList as we add elements to it. Here getCapacity method gives capacity of ArrayList using reflection api.Here elementData in the getCapacity method is instance variable of java.util.ArrayList class.

public static void main(String args[]){
   ArrayList<String> list = new ArrayList<String>();
   list.add("a");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("b");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("c");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("d");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("e");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("f");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("g");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("h");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("i");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("j");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
   list.add("k");
   System.out.println("Capacity= " + getCapacity(list)+" "+"Size = "+list.size());
}

static int getCapacity(ArrayList<?> list) throws Exception {
        Field dataField = ArrayList.class.getDeclaredField("elementData");
        dataField.setAccessible(true);
        return ((Object[]) dataField.get(list)).length;
}

Output :
Capacity = 10 Size = 1
Capacity = 10 Size = 2
Capacity = 10 Size = 3
Capacity = 10 Size = 4
Capacity = 10 Size = 5
Capacity = 10 Size = 6
Capacity = 10 Size = 7
Capacity = 10 Size = 8
Capacity = 10 Size = 9
Capacity = 10 Size = 10
Capacity = 15 Size = 11

5. ArrayList is an ordered collection 

By ordered collection ,it means that when we retrieve elements of ArrayList after inserting elements in it,the order in which elements will be retrieved will be exactly same as the order in which element would have been inserted in it.

Lets check if it is true by executing a simple program.

public static void main(String[] args) {
  List<String> list = new ArrayList<String>();
  list.add("a");
  list.add("b");
  list.add("c");
  for(int i=0;i<list.size();i++){
   System.out.println("Index:"+i+"element:"+list.get(i));
  }
  list.clear();
  System.out.println("changed Order");
  list.add("b");
  list.add("a");
  list.add("c");
  for(int i=0;i<list.size();i++){
   System.out.println("Index:"+i+"element:"+list.get(i));
  }
 }

Ouput :

Index:0 element:a
Index:1 element:b
Index:2 element:c
changed Order
Index:0 element:b
Index:1 element:a
Index:2 element:c

So we can see from above output that order in which we inserted elements in ArrayList, while retrieving it maintained same order.

6. ArrayList allows duplicates

ArrayList allows duplcate values.Lets see below example.

List<String> list = new ArrayList<String>();
list.add("GB");
list.add("GB");

System.out.println("Duplicate Values");
for(String str : list){
  System.out.println(str);
}

Output :

Duplicate Values
GB
GB

7. ArrayList allows null values

ArrayList allows null values as well.Lets see below below example.

List<String> list = new ArrayList<String>();
list.add("1");
list.add(null);
list.add(null);

System.out.println("Allows null Values");
for(String str : list){
   System.out.println(str);
}

Output :
Allows null Values
1
null
null

8. ArrayList is not synchronized 

Synchronization is the mechanism used in multi threaded environment such that only one thread can have lock on object at a time and can perform operations on the object.When we say ArrayList is not synchronized ,it means if instance of ArrayList is being used in multi threaded environment,it is possible that while one thread is adding value to it,another thread  would also be accessing this at the same time,so second thread is actually working on obsolete state of object.All the methods provided in the ArrayList class are non synchronized.However if we want to synchronize instance of ArrayList,we can do as below

We can use static synchronizedList method of Collections class.

public static void main(String[] args) {
   List<String> list = new ArrayList<String>();
  list.add("a");
  list.add("b");
  list.add("c");
  list = Collections.synchronizedList(list);
  synchronized(list){ 
   Iterator<String> itrList = list.iterator(); 
   while(itrList.hasNext()){ 
    System.out.println(itrList.next()); 
    } 
 }
}

Alternatively instead of ArrayList, we can use CopyOnWriteArrayList which is thread safe implementation of List<E> interface.

CopyOnWriteArrayList<String> al = new CopyOnWriteArrayList<String>();
 al.add("a");
 al.add("b");
 al.add("c");
 Iterator<String> iterator = al.iterator(); 
 while (iterator.hasNext())
       System.out.println(iterator.next());
 }

Hope this article was helpful to you guys. Any feedback ,suggestions, questions are most welcome.