ArrayList Internal Implementation in Java

ArrayList internal implementation in Java or how does ArrayList work internally in Java is a very important interview question. Some of the questions that may come up are-

Where does ArrayList store its element?
What is the initial or default capacity of ArrayList and how ArrayList of that capacity is created?
How does add method in ArrayList work?
How does remove method work in ArrayList?
How does ArrayList grow and shrink automatically?

In this post let’s try to answer these questions by looking into the internal implementation of ArrayList in Java.

Where does ArrayList store its element

Internally ArrayList in Java uses array to store its element. It’s an Object array which is defined as follows.

transient Object[] elementData;

Capacity of ArrayList

Initial capacity of the created ArrayList depends on the constructor used. There are 3 constructors.

ArrayList(int initialCapacity)- If initial capacity is explicitly specified while constructing an ArrayList then it is ensured that the elementData array is created with that length.

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

As you can see from this code from the ArrayList class in Java, if initialCapacity > 0 then elementData array is crated using that initial capacity.

ArrayList()- If no initial capacity is specified then the ArrayList is created with the default capacity.

Here is the code from the ArrayList class in Java.

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

If you see in the code DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as an empty array.

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

It’s only when the element is added to the ArrayList that the array is created with default capacity. Default capacity in the ArrayList class is defined as follows.

private static final int DEFAULT_CAPACITY = 10;

ArrayList(Collection<? extends E> c)- If ArrayList is constructed using an existing collection then elements of the passed collection are copied to the elementData array.

public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // replace with empty array.
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

As you can see from the code, in this statement elementData = c.toArray(); elements of the collection are returned as array.

elementData = Arrays.copyOf(elementData, size, Object[].class);

This line ensures that elementData array is converted to array of type Object.

How does add method work in ArrayList

That is where the resizable-array implementation feature of the ArrayList is covered. If you see the ArrayList internal implementation in Java, everytime add() method is called it is ensured that ArrayList has required capacity. If the capacity is exhausted a new array is created with 50% more capacity than the previous one. All the elements are also copied from previous array to new array.

When add() method is called initially there is a check to ensure the capacity.

private void ensureCapacityInternal(int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  ensureExplicitCapacity(minCapacity);
}

As you can see if default capacity ArrayList has to be created it’s here that the capacity is actually initialized as 10.

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

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

From this code, if required, grow() method is called to increase the capacity of the ArrayList.

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

As you can see right shift operator is used to increase the capacity by 50% in the following statement.

 int newCapacity = oldCapacity + (oldCapacity >> 1);

Also the elementData array is changed to have the new capacity, elements from the old array are also copied to the new array.

elementData = Arrays.copyOf(elementData, newCapacity);

So that’s how internally ArrayList keeps on growing dynamically.

How does remove method work in ArrayList

If you remove any element from an array then all the subsequent elements are to be shifted to fill the gap created by the removed element. That’s what remove method does internally in the ArrayList class in Java.

/**
 * Removes the element at the specified position in this list.
 * Shifts any subsequent elements to the left (subtracts one from their
 * indices).
 */
public E remove(int index) {
  rangeCheck(index);

  modCount++;
  E oldValue = elementData(index);

  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  elementData[--size] = null; // clear to let GC do its work

  return oldValue;
}

This is the statement which is actually shuffling the elements of the array.

System.arraycopy(elementData, index+1, elementData, index, numMoved);

So that’s how ArrayList shrinks dynamically.

How does ArrayList grow and shrink automatically

This point is already covered in the section how add and remove methods work in ArrayList.

That's all for the topic ArrayList Internal Implementation in Java. If something is missing or you have something to share about the topic please write a comment.

You may also like

KnpCode

June 21, 2022