Internal Working of ArrayList in Java
ArrayList is a resizable array implementation in java. ArrayList grows dynamically and ensures that there is always a space to add elements. The backing data structure of ArrayList is an array of Object classes. ArrayList class in Java has 3 constructors. It has its own version of readObject and writeObject methods. Object Array in ArrayList is transient. It implements RandomAccess, Cloneable, and java.io.Serializable (which are Marker Interface in Java)
public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable
Internally an ArrayList uses an Object[] Array which is an array of objects. All operation like deleting, adding, and updating the elements happens in this Object[] array.
/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. */ transient Object[] elementData; // non-private to simplify nested class access
The above code is from Java 8 in Java 7 the array is declared as a Private transient Object but in Java 8 it’s not Private because non-private is to simplify access for a nested class like Itr, ListItr, SubList.
Initialization
List arrayList = new ArrayList();
while declaring ArrayList below code is executed as the default constructor of the ArrayList class is invoked.
Hereby default capacity of the Array size is 10.
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 = <>;
Here, the List is initialized with a default capacity of 10. Array List with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is inserted into the Array list ( Adding 1st element to ArrayList).
Constructors
To create an ArrayList, First need to create an object of the ArrayList class. ArrayList contains 3 types of constructors in Java 8
- ArrayList(): This constructor is to initialize an empty List.
- ArrayList(int capacity): In this constructor, we can pass capacity as a parameter, used to initialize the capacity by the user.
- ArrayList(Collection c): In this constructor, we can pass a Collection c as a parameter, In which an Array list will contain the elements of Collection c.
ArrayList(): This constructor is used to create an empty ArrayList with an initial capacity of 10 and this is a default constructor. We can create an empty Array list by reference name arr_name object of ArrayList class as shown below.
ArrayList arr_name = new ArrayList();
Below is the internal code for this constructor(In Java 8):
// Constructs an empty Arraylist with an initial capacity of ten. public ArrayList()
In the above code, DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be changed to DEFAULT_CAPACITY when we add the first element into the array list. (DEFAULT_CAPACITY =10).
ArrayList(int capacity): This constructor is used to create an ArrayList with the initial capacity given by the user. If we want to create an ArrayList with some specified size we can pass the value through this constructor. Internally Array of objects is created with the size given by the user. For Example, if a user wants the Array list size should be 7, then the value 7 can be passed in the constructor, it can be created as shown here:
ArrayList arr = new ArrayList(7);
Below is the internal code for this constructor(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); >> In the above code, the size that can be passed into the constructor is greater than 0 (initialCapacity>0) the Array of objects created will be in the given capacity. If the capacity passed is equal to 0(initialCapacity==0) then an empty Arraylist will be created. If the initial Capacity is less than 0 (initialCapacity) then IllegalArgumentException will be thrown.
ArrayList(Collection c ): This constructor is used to create an array list initialized with the elements from the collection passed into the constructor (Collection c ). The object of the ArrayList can be created upon the specific collection passed into the constructor.
ArrayList arrayList = new ArrayList(new LinkedList());
Below is the internal code for this constructor(In Java 8):
public ArrayList(Collection 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 elements from the collection should be placed in the Array list. This code will check the size of the passed collection, If the size is greater than zero then Arrays.copyOf() method is used to copy the collection to the array. NullPointerException is thrown if the collection that passed into the constructor is null.
Java
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]
Here the elements in the arr are passed to newList. So elements of arr were copied to newList this is shown in the above example.
How the size of ArrayList grows dynamically? [add() method]
Let’s deep dive into how to add method that works in Array list with help of the internal Java 8 code of ArrayList. If we try to add an element using the add() method in the array list Internally then it checks for the capacity to store the new element or not, If not then the new capacity is calculated as shown in the internal code of the add() method.
Here in the add(Object ) method object is passed and the size is increased. Internal capacity of the array is ensured by the ensureCapacityInternal() method
private void ensureCapacityInternal(int minCapacity) < if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) < minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); >ensureExplicitCapacity(minCapacity); >
This ensureExplicitCapacity method determines what is the current size of elements and what is the maximum size of the array. here Minimum capacity will be the maximum of default capacity and mincapacity then goes for ensureExplicitCapacity method mincapacity as an argument.
private void ensureExplicitCapacity(int minCapacity) < modCount++; // overflow-conscious code if (minCapacity - elementData.length >0) grow(minCapacity); >
Here if the (mincapacity – arraylength) is greater than 0(>0) then the Array size will grow by calling the grow() method and mincapacity as the argument passed.
/** * 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 grow method in the ArrayList class gives the new size array. In Java 8 and later The new capacity is calculated which is 50% more than the old capacity and the array is increased by that capacity. It uses Arrays.copyOf which gives the array increased to the new length by right shift operator also it will grow by 50% of old capacity.
int newCapacity = oldCapacity + (oldCapacity >> 1);
For example, if the Array size is 10 and already all the rooms were filled by the elements, while we are adding a new element now the array capacity will be increased as 10+ (10>>1) => 10+ 5 => 15. Here the size is increased from 10 to 15. To increase the size by 50% we use the right shift operator. While in Java 6 it’s totally different from the above calculation on increasing the size of the Array, in java 6 the capacity increases by the amount to 1.5X
int newCapacity = (oldCapacity * 3)/2 + 1;
How does the remove method work in ArrayList? [ArrayList shrinks automatically]
To remove an element from ArrayList in Java , we can use either remove(int i) [0 index based] or remove(Object o) . while removing any element from an ArrayList, internally all the subsequent elements are to be shifted left to fill the gap created by the removed element in the array then subtracts one from their indices. size of the array will be decreased 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; >
System.arrayCopy method is used for this purpose. Here index+1 is the initial position and index is the final position. Since the element at the position index is removed so elements starting from index+1 are copied to the destination starting from the index.
System.arraycopy(elementData, index+1, elementData, index, numMoved);
This is how ArrayList shrinks automatically.
Best practices in creating ArrayList
Whenever we create an ArrayList and it reaches its threshold, Internally creates a new ArrayList object with a new capacity and copies all old elements from the old ArrayList to a new object. This process will take more space and time even it provides flexibility to do.
Threshold = (Current Capacity) * (Load Factor)
The load factor is the measure that decides when to increase the capacity of the ArrayList. The default load factor of an ArrayList is 0.75f. For example, current capacity is 10. So, loadfactor = 10*0.75=7 while adding the 7 th element array size will increase. So, It would be good practice if we choose the initial capacity, by keeping the number of expected elements in mind as approx.
Performance of ArrayList
The time complexity of the common operations in ArrayList java.
- add(): For adding a single element O(1) . Adding n element in the array list takes O(n).
- add(index, element): adding element in particular index in average runs in O(n) time.
- get(): is always a constant time O(1) operation.
- remove(): runs in linear O(n) time. We have to iterate the entire array to find the element fit for removal.
- indexOf(): It runs over the whole array and iterates through each and every element worst case will be the size of the array n .so, it requires O(n) time.
- contains(): implementation is based on indexOf(). So it will also run in O(n) time.
- The size, isEmpty, set, iterator, and listIterator operations run in constant time O(1)
- ArrayList is a resizable array implementation in java.
- The backing data structure of ArrayList is an array of Object class.
- When creating an ArrayList you can provide initial capacity then the array is declared with the given capacity.
- The default capacity value is 10. If the initial capacity is not specified by the user then the default capacity is used to create an array of objects.
- When an element is added to an ArrayList it first checks whether the new element has room to fill or it needs to grow the size of the internal array, If capacity has to be increased then the new capacity is calculated which is 50% more than the old capacity and the array is increased by that capacity.