Internal Working of ArrayList in Java

Java's version of a resizable array is called ArrayList. The dynamic growth of an array list ensures that there is always room for new elements. ArrayList's backing data structure is an array of Object class instances. Java's ArrayList class contains three constructors. Its own readObject and writeObject methods exist. ArrayList's object array is a momentary object. Cloneable, Randomaccess, and java.io are all implemented. Serializable (which are Marker Interface in Java) (which are Marker Interface in Java)

Syntax:

public class ArrayList<A>
extends AbstractList<A>
implements List<A>, RandomAccess, Cloneable, java.io.Serializable

An Object[] Array, an array of objects, is used internally by an ArrayList. This Object[] array is where all operations like deleting, adding, and modifying elements take place.

Initialization:

List<String>AL = new AL<String>();

The default function Object() { [native code] } of the ArrayList class is called when the ArrayList class is declared, which causes the code below to run.

In Java 7

public AL() {

     this (20);

}

We are declaring default size as 20

In Java 8

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

// Shared empty array instance used for empty instances.

private static final Object[] EMPTY_ELEMENTDATA = {};

  /**

   * Shared empty array instance used for default sized empty instances. We

   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when

   * first element is added.

   */

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

This initialization of the List gives it a default capacity of 10. When the first element is placed into an array list with elementData == DEFAULTCAPACITY EMPTY ELEMENTDATA, the array list will be enlarged to DEFAULT CAPACITY (Adding 1st element to ArrayList).

Constructors

To create an ArrayList, first need to create an object of the ArrayList class. Java 8 has three different sorts of constructors for ArrayList.

• ArrayList(): Use this function Object() { [native code] } to start off with a blank list.
• ArrayList(int capacity): This function Object() { [native code] } allows us to pass the capacity parameter, which the user will use to initialise the capacity.
• ArrayList(Collection c): This function Object() { [native code] } allows us to pass a Collection c as a parameter. The items of the Collection c will be contained in an Array list.

ArrayList():

This function Object() { [native code] }, which is the default function Object() { [native code] }, can be used to build an empty ArrayList with a size of 10. By referencing the name arr name object of the ArrayList class, as demonstrated below, we may build an empty array list.

ArrayList arr_name = new ArrayList();  
     In Java 8
public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

When we add the first element to the array list in the code above, DEFAULTCAPACITY EMPTY ELEMENTDATA will change to DEFAULT CAPACITY. (10 is the default capacity).

ArrayList(int capacity):

With the initial capacity specified by the user, an ArrayList is created using this function Object() { [native code] }. We can feed the value via this function Object() { [native code] } to generate an ArrayList of a particular size. Arrays of objects are internally constructed with the size specified by the user.

For instance, if a user specifies that the size of the array list should be 7, the value 7 can be supplied to the function Object() { [native code] }, and it can then be produced as follows:

          ArrayList arr = new ArrayList(7);
         In Java 8
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);
       }
}

The Array of objects produced in the code above will be in the specified capacity because the size that can be passed into the function Object() { [native code] } is more than 0 (initialCapacity>0). An empty Arraylist will be produced if the capacity supplied is equal to 0 (initialCapacity==0). IllegalArgumentException will be generated if the starting Capacity is less than 0 (initialCapacity0).

ArrayList(Collection<? extends E> c ):

The components from the collection provided to the function Object() { [native code] } are utilised to initialise an array list created by this function Object() { [native code] } (Collection c ). The exact collection supplied into the function Object() { [native code] } can be used to produce the object of the ArrayList.

ArrayList<String> arrayList = new ArrayList<String>(new LinkedList());
In Java 8
public ArrayList(Collection<? extends E> c) {
       elementData = c.toArray();
       if ((size = elementData.length) != 0) {


           // c.toArray might (incorrectly) not return Object[] 
           if (elementData.getClass() != Object[].class)
               elementData = Arrays.copyOf(elementData, size, Object[].class);
       } else {


           // replace with empty array.
           this.elementData = EMPTY_ELEMENTDATA; 
       }
   }

The collection's elements ought to be added to the Array list. This code will determine the collection's size and switch to arrays if the size is more than zero. The collection is copied to the array by using the copyOf() function. If the collection that was supplied into the function Object() { [native code] } is null, NullPointerException is raised.

//
import java.util.ArrayList;
import java.util.Collection;


public class Main {
    public static void main(String args[])
    {
        Collection<Integer> arr = new ArrayList<Integer>();
        arr.add(1);
        arr.add(2);
        arr.add(3);
        arr.add(4);
        arr.add(5);
        System.out.println("This is arr " + arr);
        ArrayList<Integer> newList
            = new ArrayList<Integer>(arr);
        System.out.println("This is newList " + newList);
        newList.add(7);
        newList.add(700);
        System.out.println(
            "This is newList after adding elements "
            + newList);
    }
}

Output:

This is arr [1, 2, 3, 4, 5]
This is newList [1, 2, 3, 4, 5]
This is newList after adding elements [1, 2, 3, 4, 5, 7, 700]

The elements from the arr are supplied to newList in this case. As can be seen in the example above, elements of arr were transferred to newList in this manner.

Declaring ArrayList dynamically:

With the aid of the internal Java 8 code of ArrayList, let's take a closer look at how to create a function that operates in an array list. The array list internally checks to see whether there is enough space to accommodate the new element when we try to add it using the add() function. If not, the new capacity is determined as indicated in the add() method's internal code.

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

Here, the size is expanded by passing an object to the add(Object) function. The ensureCapacityInternal() function guarantees the array's internal capacity.

private void ensureCapacityInternal(int minCapacity) {


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

The current size of the elements and the array's maximum size are determined by the ensureExplicitCapacity method. Here Maximum default capacity will be the minimum capacity, and mincapacity will use mincapacity as an input in the ensureExplicitCapacity method.

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


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

In this case, the array size will increase by using the expand() function and passing the mincapacity parameter if (mincapacity - arraylength) is more than 0 (>0).

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

The new size array is provided by the grow function in the ArrayList class. In Java 8 and later, the array is expanded by the new capacity, which is 50% larger than the previous capacity. It makes use of Arrays.copyOf, which increases the array's length by using the right shift operator while simultaneously increasing its capacity by 50%.

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

When we add a new element to an array with a size of 10, for instance, and all of the rooms have already been occupied by the elements, the array's capacity will grow to 10+ (10>>1) => 10+ 5 => 15. The size is raised from 10 to 15 in this instance. By using the right shift operator, we may expand the size by 50%. Java 6 completely differs from the estimate made previously when increasing the size of the Array since it increases capacity by 1.5X.

int newCapacity = (oldCapacity * 3)/2 + 1;

Remove method in ArrayList:

In Java, we may use remove(int I [0 index based] or remove(Object o) to remove an entry from an array list. When an element is deleted from an array list, all succeeding entries must internally be moved to the left to cover the empty space left by the removed element, and then their indices must be reduced by one. The array's size will be reduced by 1. ( – – size).

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

For this, the System.arrayCopy method is employed. The initial position in this case is index+1, and the final position is index. Due to the removal of the element at index, elements beginning at index+1 are copied to the destination starting at index.

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

Creating ArrayList:

Internally produces a new ArrayList object with a new capacity whenever we build an ArrayList and it hits its threshold. It then copies all of the old elements from the old ArrayList to the new object. Even while it allows more flexibility, this method will require more room and time.

Threshold:

Threshold = (Current Capacity) * (Load Factor)

When to raise the capacity of the ArrayList is determined by the load factor. An ArrayList has a load factor by default of 0.75f. For instance, the present capability is 10. As a result, the array size will grow as loadfactor = 10*0.75=7 while the seventh member is added. Therefore, it would be wise to set the beginning capacity while roughly considering the expected number of components.

Performance of ArrayList:

• add(): O(1) for adding one element. It takes O to add n elements to the array list (n).
• Addition of an element to a certain index takes on average O(n) time.
• Get() always runs in O(1) constant time.
• Remove() takes linear O(n) time to execute. To locate the element suitable for removal, we must iterate the entire array.
• The worst case for indexOf() is the array size n, therefore it takes O(n) time to run over the entire array and iterate through each element.
• Implementation of contains() is based on indexOf (). Since it runs in O(n) time, it will also.
• The constant time O operations for size, isEmpty, set, iterator, and listIterator (1)