Java – ArrayList Internal Implementation

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

transient Object[] elementData;

1. Very First step : Declaration of ArrayList

When we declare an arraylist, we define a constructor, hence defining a capacity for the arraylist.

If we create Arraylist using Default constructor, then the capacity will be calculated in a way like this, see the code below:

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

where DEFAULTCAPACITY_EMPTY_ELEMENTDATA is defined as an empty array, like this, see the code below:

      
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 

      
private static final int DEFAULT_CAPACITY = 10;

If we create Arraylist constructor by passing the capacity, then the capacity will be calculated in a way like this, see the code below:

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

See in the code above, the condition if(initialCapacity>0) then it will create an array elementData of size of that very capacity which was passed.

If we create ArrayList from another collection, then elements of passed collection are copied to elementData array.

        
elementData = c.toArray();

see the code below:

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

If you see in this code above, you will notice that the elementData array(or passed collection) is converted to an array of type Object.

2. add() : What happens next when you add an element ?

The below code gets called.

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

which at first ensures the capacity of the arraylist, then adds the elements to the end of the list. 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.

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

  ensureExplicitCapacity(minCapacity);
}  

As you can see it’s here that the capacity is actually initialized as 10, if required to set to default.

          
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.

3. remove() : What happens when you remove an element ?

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.

See the code below:

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

So that is how an arraylist grows and reduces in size dynamically.

So here we are, we hope now you are confident and know how to use ArrayList in java.

We tried our best to simplify the explanation, if you feel any difference or you need help in understanding any such thing, then feel free to contact us through email and subscribe to ProgrammerToday.

---