Tech Master Tutorials
Email Facebook Google LinkedIn Pinterest Twitter
Home Java Java 8 Java Interview Questions Java Programming

ArrayList

Internal Implementation details of ArrayList:

ArrayList is a Dynamic/Resizable-array implementation of the List interface. ArrayList implements the List interface methods. Also provides methods to manipulate the internal array used to hold the data.
ArrayList uses an array Internally. Initially array is initialised with an initial default capacity that is 10. elementData[] array of object type is used to store the elements.
When the ArrayList is created with the default constructor initial size of the elementData[] array is 0.
Following is the default constructor of the ArrayList class.

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



Adding an element to the arraylist :

In this case while adding the first element, when ArrayList class checks to ensure the capacity then array size is increased with the default capacity as before adding any element ensureCapacityInternal() function is called which checks for the capacity and checks if elementData= DEFAULTCAPACITY_EMPTY_ELEMENTDATA then increases the capoacity by DEFAULT_CAPACITY or minCapacity(size+1) whichever is greater out of which initialy DEFAULT_CAPACITY is greater.

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

After the addition of first element if internal array reaches its maximum capacity then array size is increased with its half of the current size. So if current size is n then size of the new array will be the 1.5n. Also before increasing the sizd of the array it is also checked if array size has reached the maximum array size possible i.e Integer.MAX_VALUE – 8 represented by the constant MAX_ARRAY_SIZE.

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Function to grow the array size :

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



Removing an element from the arraylist :

Before removing an element by the index it checks for the index if it is out of bound using the below function.

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

And it removes the element using System.arraycopy(elementData, index+1, elementData, index, numMoved) function by copying the index+1 index onwards elements to the one position left. Same in case of remove by Object, find the index and move elements to one position left.




Synchronization:

ArrayList is not synchronized. If multiple threads are going to access the arrayList concurrently then we need to keep it synchronized. ArrayList can be synchronized externally. It can be "wrapped" using the Collections.synchronizedList() method.

List list = Collections.synchronizedList(new ArrayList());

Or we can use the Vector that is synchronized.