In this post we will see How ArrayList works internally in Java. We will see how add() method works, what logic it has been implemented inside add() methods. Also we will see how size increase dynamically in case of ArrayList.
Let’s see an example where we will add and remove some element in List.
import java.util.ArrayList;
import java.util.List;
public class ArraListExample {
public static void main(String[] args) {
List<String> listObject = new ArrayList<>();
listObject.add("ram");
listObject.add("mohan");
listObject.add("shyam");
listObject.add("mohan");
listObject.add("ram");
System.out.println("elements are " + listObject);
System.out.println("after removing one element shyam ");
listObject.remove("shyam");
System.out.println(listObject);
}
}
Output is –
elements are [ram, mohan, shyam, mohan, ram]
after removing one element shyam
[ram, mohan, mohan, ram]
Let’s see what happens when we create an object using new ArrayList() –
- The default capacity of ArrayList is 10(Don’t forget we are going to use this later).
/** * Default initial capacity. */ private static final int DEFAULT_CAPACITY = 10;
- We create a list object using the default constructor, in the default constructor, It has been initialized elmentsData with DEFAULTCAPACITY_EMPTY_ELEMENTDATA something like below.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- Here elementData is a transient variable and DEFAULTCAPACITY_EMPTY_ELEMENTDATA is an empty array type of Object.
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
How add(E e) method works internally –
- add() method has been implemented as below.
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
- size is a private variable which has a default value zero. when we add the first element ensureCapacityInternal () will further get called with argument one as value. Let’s see ensureCapacityInternal() implementation.
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
- Since we have created list object using the default constructor elementData and DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be same and we will have minCapacity 10. How? Don’t forget we have constants DEFAULT_CAPACITY having value 10, Math.max(10,1) will be 10. Now we have another method ensureExplicitCapacity(minCapacity) which will get invoked. Let’s see the internal implementation of ensureExplicitCapacity(minCapacity).
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
- In the above code snippet, we are already familiar with minCapacity and elementData. We have two new things, the first one is the modCount and the second one grow(minCapacity) method. For now, keep in mind modCount used while iterating using Iterator and ListIterator. Here if condition will be satisfied or not? Yes. Since minCapcity is 10 and elementData.length will 0 and grow() method will get called. Let’s see what happen inside grow(minCapacity) method?
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);
}
- Here oldCapacity will be zero and after execution of this line number 3.The value of newCapacity will be zero after execution of line 4 becuase the code int newCapacity = oldCapacity + (oldCapacity >> 1) , newCapacity will be o only. Since newCapacity is 0 and minCapacity is 10, if condition(line number 5) will true and newCapacity is 10 now(after line 6). If condition line 7 will not true because MAX_ARRAY_SIZE value is too much. Till now elementData is an empty array, capacity will decide now i.e 10.
- Here it is very important to understand what this code int newCapacity = oldCapacity + (oldCapacity >> 1) is doing. Suppose we have oldCapacity is 10, then what will value of newCapacity, let’s see small example –
public class CollectionsExample {
public static void main(String[] args) {
int newCapacity = 10 + (10 >> 1);
System.out.println(newCapacity);
}
}
[stextbox id=’info’]The output is 15. This is how ArrayList grow dynamically. Initial capacity is 10 and once we have 10 elements the new capacity will increase one and half times i.e 15.[/stextbox]
- Let’s come back to add() method
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
- ensureCapacityInternal() has been executed, the element which we are adding it will assign to elementData and size will increase. The same process will repeat when we will add another element and so on. So what is happening inside hugeCapacity() and what is the value of MAX_ARRAY_SIZE constant.
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- Let’s see about MAX_ARRAY_SIZE. It is defined as constant inside the ArrayList class.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- Let’s see what is its value in the below example.
public class CollectionsExample {
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public static void main(String[] args) {
System.out.println(MAX_ARRAY_SIZE);
}
}
Output is –
- We can see the value of MAX_ARRAY_SIZE is 2147483639 which is too high. hugeCapacity() will only execute when we will have more than 2147483639 elements in our list which is very rare.
Let’s integrate the things together, define custom ArayList.
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Iterator;
public class CustomArrayListExample extends AbstractList {
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
protected transient int modCount = 0;
CustomArrayListExample() {
elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
@Override
public boolean add(Object e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public static void main(String[] args) {
CustomArrayListExample arrayListExample = new CustomArrayListExample();
arrayListExample.add("ram");
arrayListExample.add("mohan");
arrayListExample.add("sohan");
System.out.println("just print the list elements---");
System.out.println(arrayListExample);
Iterator it = arrayListExample.iterator();
System.out.println("Using iterator---");
while (it.hasNext()) {
System.out.println(it.next());
}
System.out.println("Using for-each loop---");
for (Object str : arrayListExample) {
System.out.println(str);
}
}
@Override
public Object get(int index) {
rangeCheck(index);
return elementData[index];
}
public void rangeCheck(int index) {
if (index >= size) {
throw new IndexOutOfBoundsException();
}
}
@Override
public int size() {
return size;
}
}
Output is –
just print the list elements—
[ram, mohan, sohan]
Using iterator—
ram
mohan
sohan
Using for-each loop—
ram
mohan
sohan
This is all about How ArrayList works internally in Java.
You may like –
