Monday, 3 August 2015

How ArrayList works internally in Java

ArrayList arguably would be the most used collection along with the HashMap. Many of us programmers whip up code everyday which contains atleast one of these data structures to hold objects. I have already discussed how HashMap works internally in Java, in this post I'll try to explain how ArrayList works in Java.

As most of us would already be knowing that ArrayList is a Resizable-array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it. So let's see what is the backing data structure for an ArrayList and how it grows dynamically and ensures that there is always room to add elements. Because of all these side questions it is also a very important Java Collections interview question.

Note - Code of ArrayList used here for reference is from Java 8.

Where does ArrayList store elements

Basic data structure used by ArrayList to store objects is an array of Object class, which is defined like -

transient Object[] elementData;

I am sure many of you would be thinking why transient and how about serializing an ArrayList then?
ArrayList provides its own version of readObject and writeObject so no problem in serializing an ArrayList and that is the reason, I think, of making this Object array as transient.

What happens when ArrayList is created

ArrayList class provides 3 constructors to create an array list.

  • public ArrayList(int initialCapacity) - When this constructor is used we can provide some internal capacity rather than depending on the default capacity as defined in the ArrayList class.
    As example -
    List<String> myList = new ArrayList<String>(7);
    
    Code in the ArrayList class is as -
    public ArrayList(int initialCapacity) {
         if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
         } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
         } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
         }
    }
    

    Where EMPTY_ELEMENTDATA is defined as -

    private static final Object[] EMPTY_ELEMENTDATA = {};
    

    It is easy to see here, that if provided capacity is greater than zero then the elementData array will be created with that capacity, in case provided capacity is zero then elementData array is initialized with an empty Object array. In this case ArrayList will grow when first element is added.

  • public ArrayList() - In case default constructor is used i.e. ArrayList is created like -
     myList = new ArrayList();
    

    Code in the ArrayList class is as -

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    

    Where DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    

    So you can see initially it will be initialized with an empty array, it will grow only when first element is added to the list.

  • public ArrayList(Collection<? extends E> c) - If we want to construct a list containing the elements of the specified collection we can use this constructor. In this constructor implementation checks for the length of the collection passed as parameter, if length is greater than zero then Arrays.copyOf method is used to copy the collection to the elementData array.
    elementData = Arrays.copyOf(elementData, size, Object[].class);
    

How does ArrayList grow dynamically

When we add an element to an ArrayList it first verifies whether it has that much capacity in the array to store new element or not, in case there is not then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that much capacity (Actually uses Arrays.copyOf which returns the original array increased to the new length).

Code is like this -

public boolean add(E e) {
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     elementData[size++] = e;
     return true;
}
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

Where DEFAULT_CAPACITY is defined as -

private static final int DEFAULT_CAPACITY = 10;
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
       grow(minCapacity);
}

You can see here it is determined if there is a need to increase the size of the array, if yes then grow method is called.

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);
}

Note that till Java 6 the new capacity calculation used to be like this -

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

Which is changed from Java 7 to use right shift operator. With right shift operator also it will grow by 50% of old capacity.
Let's see it with the help of a small program

public class Test {
    public static void main(String args[])  {
       int a = 10;
       System.out.println(a>>1);   
    }    
}

Output

5

If the default capacity was 10 then

 
int newCapacity = oldCapacity + (oldCapacity >> 1);
will return 15.

What happens when element is removed

When elements are removed from an ArrayList using either remove(int i) (i.e using index) or remove(Object o), in the underlying array the gap created by the removal of an element has to be filled. That is done by Shifting any subsequent elements to the left (subtracts one from their indices). System.arrayCopy method is used for that.
System.arraycopy(elementData, index+1, elementData, index, numMoved);

Here index+1 is the source position and index is the destination position. Since element at the position index is removed so elements starting from index+1 are copied to destination starting from index.

That's all for this topic how ArrayList internally works in Java. If you have any doubt or any suggestions to make please drop a comment. Thanks!


Related Topics

  1. How HashMap internally works in Java
  2. How Linked List class works internally in Java
  3. How HashSet works internally in Java
  4. How to sort arraylist of custom objects in Java
  5. Java Collections interview questions
  6. CopyOnWriteArrayList in Java

You may also like -

7 comments:

  1. it is nice to explain about ArrayList in Java but could you please put some Examples to understand how it works ?

    thanks alot
    Java Developer

    ReplyDelete
  2. How is that i can iterate and remove an element at the same time from an LinkedList using the remove() method, but i cannot do it for an ArrayList.

    ReplyDelete
  3. where the elementData variable is declared....?

    ReplyDelete