ArrayList Implementation in Java

ArrayList is a class of Java Collection framework. It uses a dynamic array for storing the objects. It is much similar to Array, but there is no size limit in it. We can add or remove the elements whenever we want. We can store the duplicate element using the ArrayList; It manages the order of insertion internally.

The ArrayList class is much more flexible than the traditional Array. It implements the List interface to use all the methods of List Interface. It takes place in java.util package.

The ArrayList class inherits the AbstractList class and implements the List Interface. The elements of it can be randomly accessed. It can not be used for primitive types such as int, char, etc.; for these data types, we need a wrapper class.

The difference between Array and ArrayList is that Arraylist provides a dynamic array that can be expanded when needed. In Array, we have to specify the size of the Array during initialization, but it is not necessary for ArrayList. By default, it takes its size to 10.

ArrayList class can be declared as follows:

  public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable    

ArrayList can be defined as follows:

Consider the below example:

  import java.util.*;  public class ALExample {  public static void main(String[] args) {  List l = new ArrayList<>(); //List Implementation  l.add(“Sam”);  //adding objects to list  l.add(“Sandy”);  l.add(“Joe”);  l.add(“Arya”);  l.add(“Nik”);  System.out.println(“List objects are:  ” +l); // printing the list  l.remove(“Nik”); //removing objects from list  System.out.println(“After Removing Nik, List Objects are” +l);  }  }  

Output:

List objects are:  [Sam, Sandy, Joe, Arya, Nik]  After Removing Nik, List Objects are[Sam, Sandy, Joe, Arya]

From the above example, we can see how we can add or remove the List’s objects.

Let’s understand how it works internally:

ArrayList Implementation in Java

How ArrayList Works Internally

When we initialize an ArrayList using the below syntax:

It creates an Array with the default capacity, which is 10. It invokes the default constructor of the ArrayList class. It uses an empty array instance to create the new object, and the following code is executed by the Java compiler:

in Java 7 or previous version:

in Java 8 or later version:

  private static final Object[] EMPTY_ELEMENTDATA = {}; //Initiliazing the arraylist EMPTY_ELEMENTDATA  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //  Initializing it with the default capacity 10   public ArrayList() {          this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // here, this keyword is returning the instance of ArrayList      }  

From the above code, we can see an empty ArrayList is internally created with the default capacity, which is 10. when we add the first element in it, it will be expanded to DEFAULT_CAPACITY.

ArrayList uses an Object [] Array to add, remove, and traverse the element.

for the prior versions of Java than Java 8, it specifies the objects as follows:

As we can see from the above line of code, from Java 8, the private keyword has been removed for providing access to nested classes such as Itr, ListItr, SubList.

We can also define the List with the specific capacity. When we provide an initial capacity, the ArrayList constructor is invoked internally to specify the Array internally. For example, if we define an array list with the capacity of 20, we have to define the ArrayList as follows:

Then the following code will be executed by the Java compiler:

In Java 7 or previous versions:

    public ArrayList(int initialCapacity)  //ArrayList constructor invokes with the intialCapacity argument for the specified Array  {   super();          if (initialCapacity < 0)  //if the value is less than 0, it will throw IllegalArgumentException              throw new IllegalArgumentException(“Illegal Capacity: “+                                                 initialCapacity);  this.elementData = new Object[initialCapacity];      }  

From the above code, we can see the array size will be equal to the specified Array.

In Java 8 or later versions:

  public ArrayList(int initialCapacity) //ArrayList Constructor invokes with the initialCapacity argument for the initial Array  {          if (initialCapacity > 0) {  //if the value is grater than 0, it will create a new object              this.elementData = new Object[initialCapacity]; // new object creation          } else if (initialCapacity == 0) {              this.elementData = EMPTY_ELEMENTDATA;          } else {              throw new IllegalArgumentException(“Illegal Capacity: “+                                                 initialCapacity); // if the value is <= 0, it will throw an IllegalArgumentException          }      }  

From the above code, we can see the array size will be equal to the specified Array.

We can also create an object of ArrayList for a specific collection by executing the below line of code:

The above code will create a non-empty list having the objects of LinkedList.

How the ArrayList Grows Dynamically

When we add a new object to the ArrayList, it will check for the initial size of the ArrayList whether it has space or not. If there is enough space for the new object, it will add simply using the add() method. If there is not enough space to add a new object, it will dynamically increase the size of the Array by that much capacity.

Consider the below implementation of add method (In Java 7 or later):

  public boolean add(E e) {          ensureCapacityInternal(size + 1);  //  modCount!! increments          elementData[size++] = e;          return true;      }    private void ensureCapacityInternal(int minCapacity) // Detemining the current size of occupied elements  {          if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {              minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // here, Math.max will  return the maximum or largest value from the given arguments DEFAULT_CAPACITY AND minCapacity          }             ensureExplicitCapacity(minCapacity);      }    private void ensureExplicitCapacity(int minCapacity) {          modCount++; //modCount increases             // overflow-conscious code          if (minCapacity – elementData.length > 0)              grow(minCapacity);      }        private void grow(int minCapacity) // The grow method expands the size of the Array  {          // 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 will be close to the size of the array          elementData = Arrays.copyOf(elementData, newCapacity); // The Arrays.copyOf will copy the specified array      }  

from the above code,

The ensureCapacityInternal() is used to determine the current size of occupied objects and maximum size of Array.
The grow method is used to expand the new size of Array.
The minCapacity determines the current size of the objects; it includes the new specified elements.
Arrays.copyOf used to copy the specified Array.
Math.max is used to return the maximum or largest value from the passed arguments.

Performance of ArrayList

In the ArrayList, the add operation requires o(n) time; other operations are run in linear time.

The size, isEmpty, get, set, iterator, and listIterator tasks run in a constant time of O(1).

Summary

ArrayList is a customizable array implementation; we can dynamically add objects in the List.
ArrayList uses an Object class array to store the objects.
By default, ArrayList creates an array of size 10.
While initializing the Array, we can specify the size of Array.
When adding or removing elements, the space in the Array will automatically be adjusted.

Next TopicConvert ArrayList to String Array in Java

ArrayList Implementation in Java

ArrayList Implementation in Java

How ArrayList Works Internally

How the ArrayList Grows Dynamically

Performance of ArrayList

Type Handling Annotations in Jackson

Bucket Sort in Java

You may also like