Interview Question #10 How ArrayList works internally in java?

Another favorite interview question. Honestly whole of Collections is an interesting topic and a lot of interview questions can be framed on it. Advantage of this being, Java knowledge of Candidate is tested along with his/her data structure knowledge.

So lets understand how ArrayList works. This is the most basic question you could frame. Many other questions to come are based on this.

Basic Data Structure used in an ArrayList is -

private transient Object[] elementData; 

So it's an array of Object(Just the declaration.)
When we actually create an arrayList following piece of code is executed -


this.elementData = new Object[initialCapacity];


You create an ArrayList as follows -

• List<String> myList = new ArrayList<String>();  OR 
• List<String> myList = new ArrayList<String>(6); 

 1st one invokes a default constructor while the second will invoke a constructor with an integer argument. When we create an ArrayList in the 2nd way it will internally create an array of Object with size specified in the constructor argument(6 in our case). Default value is 10 i.e if no size is supplied array with size 10 is created.

Code for it is as follows -

    public ArrayList(int initialCapacity) {
    super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
    this.elementData = new Object[initialCapacity];
    }



    public ArrayList() {
    this(10);
    } 

Once you tell this interviewer can be sure you know what data structure is internally used.Now we know ArrayList is better than normal arrays as it is size dynamically increases. But how does this take place internally? How much does the size increase?

Inside .add() method there is this check. Before adding element into the array it will check what is the current size of filled elements and what is the maximum size of the array. If size of filled elements is greater than maximum size of the array(or will be after adding current element) then size of the array must be increased. But if you know array basic you cannot dynamically increase the array size. So what happens internally is a new Array is created with size 1.5*currentSize and the data from old Array is copied into this new Array.

Code for it is as follows -

    public boolean add(E e) {
    ensureCapacity(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
    }



    public void ensureCapacity(int minCapacity) {
    modCount++;
    int oldCapacity = elementData.length;
    if (minCapacity > oldCapacity) {
        Object oldData[] = elementData;
        int newCapacity = (oldCapacity * 3)/2 + 1;
            if (newCapacity < minCapacity)
        newCapacity = minCapacity;
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
    }
    }

If you wish to know more you can view the ArrayList Sourecode. In Eclipse press Ctrl+T(Open Type) and type in ArrayList. Open it to view the source code.To visualize the ArrayList class refer to following image -

Related Links

• Understanding how HashMap and HashSet work in Java