In this post, I am going to demonstrate how the size of the ArrayList increases dynamically?
The ArrayList size increases dynamically because whenever the ArrayList class requires to resize then it will create a new array of bigger size and copies all the elements from the old array to the new array. And now it is using the new array’s reference for its internal usage. As the old array is no longer in use, it will be garbage collected in the next garbage collection.
Let's see how ArrayList size increases dynamically in detail.
How ArrayList Grows Dynamically?
As we know that Array is fixed length data structure and once it is created, we can't change its size but ArrayList can re-size itself when gets full depending upon capacity and load factor.
Basically, the ArrayList is a resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null.
Let's create an example of ArrayList with default Constructor to know the default size of 10.
Create an ArrayList Example - usage of add() method
public class CreateArrayListExample {
public static void main(String[] args) {
// Creating an ArrayList of String using
List<String> animals = new ArrayList<>();
// Adding new elements to the ArrayList
animals.add("Lion");
animals.add("Tiger");
animals.add("Cat");
animals.add("Dog");
System.out.println(animals);
// Adding an element at a particular index in an ArrayList
animals.add(2, "Elephant");
System.out.println(animals);
}
}
Output:
[Lion, Tiger, Cat, Dog]
[Lion, Tiger, Elephant, Cat, Dog]
From the above example, the default constructor is used to create an ArrayList instance.
new ArrayList<>(); - Constructs an empty list with an initial capacity of ten.
ArrayList internal Implementation
Let’s take a look at, what is present inside the ArrayList class. We will be looking at implementations according to Java 8.
Steps to see in the internal implementation of an ArrayList class
- Find the DEFAULT_CAPACITY of the ArrayList
- ArrayList increase the size dynamically while adding the elements to it, so look at the internal working of add() method.
- Look at source code of ArrayList and how it grows its size?
This source code is copied from ArrayList implementation class to demonstrate how ArrayList grows dynamically(JDK 8 version).
Find the DEFAULT_CAPACITY of the ArrayList
Observe the DEFAULT_CAPACITY instance variable in aisigned with value 10.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
Internal working add() method
As more and more elements are added to the ArrayList, the size of the array keeps on increasing. How does that happen ?
Lets take a look at the add method :
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Also look at how ArrayList inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Whenever the add method is called, it makes a internal call to the private ensureCapacityInternal method and passes existing size+1 as a method argument.
The ensureCapacityInternal() method internally makes a call to private ensureExplicitCapacity(int minCapacity) method.
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
The ensureExplicitCapacity() checks the condition theminCapacity - elementData.length > 0 , if it is true then it calls the grow() method to increase the size.
The grow method creates a new Array of size int newCapacity = oldCapacity + (oldCapacity >> 1) and then copy all the elements in the new array from the older one.
/**
* 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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
So the backing array is not growing, every time when it is full, The ArrayList class is creating a new array of bigger size and copies all the elements from the old array to the new array. And now it is using the new array’s reference for its internal usage. As the old array is no longer in use, it will be garbage collected in the next garbage collection.
Do comment, if you have any doubts in this demonstration.
Learn and master Java Collections at Java Collections Tutorial
Free Spring Boot Tutorial | Full In-depth Course | Learn Spring Boot in 10 Hours
Watch this course on YouTube at Spring Boot Tutorial | Fee 10 Hours Full Course