How the Size of the ArrayList Increases Dynamically?

In this post, I am going to demonstrate how the size of the ArrayList increases dynamically?

 
The ArrayList size increases dynamically because whenever the ArrayList class requires to resize then it will create a new array of bigger size and copies all the elements from the old array to the new array. And now it is using the new array’s reference for its internal usage. As the old array is no longer in use, it will be garbage collected in the next garbage collection.

 
Let's see how ArrayList size increases dynamically in detail.

How ArrayList Grows Dynamically?

As we know that Array is a fixed-length data structure and once it is created, we can't change its size but ArrayList can re-size itself when gets full depending upon the capacity and load factor.

Let's create an example of ArrayList with default Constructor to know the default size of 10. 

Create an ArrayList Example - usage of add() method

public class CreateArrayListExample {

    public static void main(String[] args) {
        // Creating an ArrayList of String using
     List<String> animals = new ArrayList<>();
        // Adding new elements to the ArrayList
        animals.add("Lion");
        animals.add("Tiger");
        animals.add("Cat");
        animals.add("Dog");

        System.out.println(animals);

        // Adding an element at a particular index in an ArrayList
        animals.add(2, "Elephant");

        System.out.println(animals);
    }
}

Output:

[Lion, Tiger, Cat, Dog]
[Lion, Tiger, Elephant, Cat, Dog]

From the above example, the default constructor is used to create an ArrayList instance.
new ArrayList<>(); - Constructs an empty list with an initial capacity of ten. 

ArrayList internal Implementation

Let’s take a look at, what is present inside the ArrayList class. We will be looking at implementations according to Java 8. 

Steps to see in the internal implementation of an ArrayList class

1. Find the DEFAULT_CAPACITY of the ArrayList
2. ArrayList increases the size dynamically while adding the elements to it, so look at the internal working of add() method.
3. Look at the source code of ArrayList and how it grows its size?

This source code is copied from the ArrayList implementation class to demonstrate how ArrayList grows dynamically(JDK 8 version).

Find the DEFAULT_CAPACITY of the ArrayList

Observe the DEFAULT_CAPACITY instance variable in assigned with value 10.

 /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

Internal working add() method

As more and more elements are added to the ArrayList, the size of the array keeps on increasing. How does that happen?

Let's take a look at the add method :

/**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

Also, look at how ArrayList inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

Whenever the add method is called, it makes an internal call to the private ensureCapacityInternal method and passes the existing size+1 as a method argument. 

The ensureCapacityInternal() method internally makes a call to the private ensureExplicitCapacity(int minCapacity) method.

 private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

The ensureExplicitCapacity() checks the condition theminCapacity - elementData.length > 0 , if it is true then it calls the grow() method to increase the size.

The grow method creates a new Array of size int newCapacity = oldCapacity + (oldCapacity >> 1) and then copies all the elements in the new array from the older one.

 /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    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);
    }
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

So the backing array is not growing, every time when it is full, The ArrayList class is creating a new array of bigger size and copies all the elements from the old array to the new array. And now it is using the new array’s reference for its internal usage. As the old array is no longer in use, it will be garbage collected in the next garbage collection.