Internals of ArrayList (Part 1)

Note: jdk used is jdk1.6

In this practical tutorial we will try to understand the internal working of ArrayList. When you create an ArrayList , it creates an private array named elementData of length 10. ArrayList of size zero but capacity 10.

Demo1:

import java.util.ArrayList;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class Demo1 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
}

}

The internal datastructure of ArrayList is array. The list displays [] because the overriden toString method is displaying data using Iterator and on the basis of size.

When you add element to ArrayList it checks whether the new element can fit or get inserted in existing array. It does this using ensureCapacity function.

Demo2:

import java.util.ArrayList;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class Demo2 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("data1");
}
}

Now lets understand what happens when the existing array is full and how does it create a new array.

Demo3:

import java.util.ArrayList;
/**
 *
 * @author Ganesh.Rashinker
 *
 */
public class Demo3 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
for (int i = 1; i <= 10; i++) {
list.add("data" + i);
}
list.add("data11");//insert 11th element
}
}

When you add 10 elements and try to add 11th element , internally it creates a new array of length 16 using the function

Arrays.copyOf(elementData, newCapacity);

where

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

and the new arrays is referenced by elementData

elementData = Arrays.copyOf(elementData, newCapacity);

Conclusion: ArrayList uses array internally. ArrayList has the default capacity of 10 and when the internal array fills up, it creates a new array of larger capacity 16(jdk 1.6). We will understand more details of ArrayList in future posts.