-
Notifications
You must be signed in to change notification settings - Fork 0
How the Size of the ArrayList Increases Dynamically?
The ArrayList size increases dynamically because whenever the ArrayList class requires to re size then it 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.
Let's see how ArrayList size increases dynamically in detail.
As we know that Array is fixed length data structure and once it is created , we can't change it's size but ArrayList re-size itself when gets full depending upon capacity and load factor.
Basically the ArrayList is 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.
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 above example, the default constuctor is used to create a ArrayList instance. new ArrayList<>(); - Constructs an empty list with an initial capacity of ten.
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 ArrayList class
- Find the DEFAULT_CAPACITY of the ArrayList
- ArrayList increase the size dynamically while adding the elements to it so look at internal working add() method of ArrayList.
- Look at how the size of the ArrayList grows?
This source code is copied from ArrayList implementation class to demonstrate how ArrayList grows dynamically.
Observe the DEFAULT_CAPACITY instance variable in assigned with value 10.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;ArrayList increase the size dynamically while adding the elements to it so look at internal working add() method of ArrayList.
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 private ensureCapacityInternal method and passes existing size+1 as 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.