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(3); arrobj.add("Java Hungry"); arrobj.add("Blogspot"); 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
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
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
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)
{
ensureCapacity(size+1);
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
One liner answer : List
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.
In case you have any doubts regarding the internal working of add(Object) method of ArrayList in java then please mention in comments.