How Add Method Works Internally In ArrayList With Example


ArrayList is one of the most useful collection class  in Java . We have already discussed   ArrayList vs Vector , Array vs ArrayList and ArrayList vs LinkedList . Let us understand some internal details about ArrayList add(int , Object) method . How add(Object)  method works internally in ArrayList or internal implementation of add(Object) method.

How Add Method works Internally in ArrayList

Before going into the details , first look at the code example of the ArrayList add(Object) method :

public class JavaHungry {
    public static void main(String[] args)
        // TODO Auto-generated method stub
        ArrayList<Object> arrobj = new ArrayList<Object>();
        arrobj.add("Java Hungry");
        System.out.println(" is "+ arrobj);

Output : [3, Java Hungry, Blogspot]

So in the above example , we have created an ArrayList object arrobj . To add elements into the arrobj we called the add method on arrobj. After printing the arrobj , we get the desired result ,i.e , values are added to the arrobj.
But the question is how add(Object) method adds the value in ArrayList. So lets find out :

There are two overloaded add() methods in ArrayList class:

1.  add(Object)  : adds object to the end of the list.
2.  add(int index , Object )  : inserts the specified object at the specified position in the list.

As internal working of both the add methods are  almost similar. Here in this post , we will look in detail about the internal working of ArrayList add(Object) method.

Internal working of ArrayList or How add(Object) method works internally in ArrayList in Java.

ArrayList internally uses  array  object to add(or store) the elements. In other words, ArrayList is backed by Array data -structure.The array of ArrayList is resizable (or dynamic).

If you look into the ArrayList Api in jdk  rt.jar , you will find the following code snippets in it.

private transient Object[] elementData;

When you create the ArrayList object i.e new ArrayList() , the following code is executed :

this.elementData = new Object[initialCapacity];

There are two ways to create an ArrayList object . 

a. Creates the empty list with initial capacity

1.  List arrlstobj = new ArrayList();

When we create ArrayList this way , the default constructor of the ArrayList class is invoked. It will create internally an array of Object with default size set to 10.

2.  List arrlstobj = new ArrayList(20);

When we create ArrayList this way , the  ArrayList will invoke the constructor with the integer argument. It will create internally an array of Object . The size of the Object[] will be equal to the argument passed in the constructor . Thus when above line of code is executed ,it  creates an Object[] of capacity 20.

Thus , above ArrayList constructors will create an empty list . Their initial capacity can be 10 or equal to the value of the argument passed in the constructor.

b. Creates the non empty list containing the elements of the specified collection. 

List arrlstobj = new ArrayList(Collection c);

The above ArrayList constructor will create an non empty list containing the elements of the collection passed in the constructor.

How the size of ArrayList grows dynamically? 

Inside the add(Object) , you will find the following code

public boolean add(E e)
 elementData[size++] = e;
 return true;

Important point to note from above code is that we are checking the capacity of the ArrayList , before adding the element. ensureCapacity()  determines what is the current size of occupied elements and what is the maximum size of the array. If size of the  filled elements (including the new element to be added to the ArrayList class) is greater than the  maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So what happens internally is new Array is created with capacity

Till Java 6

int newCapacity = (oldCapacity * 3)/2 + 1;

(Update) From Java 7

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

also, data from the old array is copied into the new array.

Interviewer : Which copy technique internally used by the ArrayList class clone() method?

There are two copy techniques present in the object oriented programming language , deep copy and shallow copy.

Just like HashSet ,  ArrayList also returns the shallow copy of the  HashSet object. It means elements themselves are not cloned. In other words, shallow copy is made by copying the reference of the object.

Interviewer : How to create ArrayList object from arrays.

One liner answer :    List arraylistobj = Arrays.asList(arrayObject);

Interviewer : What happens if ArrayList is concurrently modified while iterating the elements ?

According to ArrayList Oracle Java docs , The iterators returned by the ArrayList class’s iterator and listiterator method are fail-fast. See the difference between fail fast and fail safe iterator .

Interviewer : What is the runtime performance of the get() method in ArrayList , where n represents the number of elements ?

get() ,set() , size() operations run in constant time i.e O(1)

add()  operation runs in amortized constant time , i.e adding n elements require O(n) time.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s