Internal Working of ArrayList in Java

Hey Folks!

I am currently working and learning on creating my own collection framework in java,i know it must be boring but my main motto,is to get the concept and the way language developers had build such things keeping in context of many aspects like memory leakages,exception handling all together and at the end building more robust software.

So,let me tell you what are you going to get from this article,

1. What happens internally when you create ArrayList.
2. How actually ArrayList dynamically grows in size.
3. Basic internal working of its CRUDE operation.

So,Before jumping to the above points,first let us have a basic understanding of ArrayList..

What is an ArrayList?

Arraylist is an class in collection framework.Basic function of any class in collection framework is to handle only objects.

So you might be thinking how this must be working?As arraylist adding 9,99,999 are of primitive types.So the reason is the compiler which does the operation known as “BOXING”,which means during time of compiling ,the compiler would convert primitive by its wrapper class i.e. for example al.add(Integer.valueOf(9)).//This is behind the scene 🤫.

So basic function of ArrayList,you can learn it from here https://beginnersbook.com/2013/12/java-arraylist/.

So lets start with our first objective,of understanding what happens when we create an ArrayList.

ArrayList has three type of constructors.Internally ArrayList uses an array of type Object,(which is static in size but obvious),so all these three constructors are revolve around initializing that internal array.Constructors along with its feature are given as follows:-

with parameter initial size of an array.

here initialCapacity is size of an array which we have initialized.

No parameters

here this constructor is initializing our internal array with default size i.e. 10.

Collection object as an parameter.

here this constructor is taken whole collection object as parameter,so at first i will initialize the size of internal array to that of collection being send,and then copy all elements of that collection into the Object array.

While Copying it does go for any loop to traverse and then copy one by one but it is essentially done by system level method that is demonstrated below

Arrays.copyOf is an method of Arrays class which internally uses System level call as here

So System.arraycopy() method will copies the source array from the position mention to the destination array from the mentioned position,that means it need 4 parameters from where to copy and from where to paste,simple as that :) edit (5th parameter is the length of an array).

How ArrayList Grows Dynamically?

So Now,Lets jump over our 2nd objective,i.e How arraylist grow dynamically as it uses static array?

You might have guess,if you have followed the above article of initializing our ArrayList.In this process we are going to use various System level methods to efficient inserting and delete elements from our array.

So,when we initialized our array using any of the above constructors,so arraylist we add up the things till it get filled up upto the size mention during initialization process.But what happen after that, So to illustrate that and give to an holistic view of it we would consider one of the CRUDE operation.

Let say add(E e) method of arraylist,where E is an Generic which defines the type of Object to be stored,this E we have mentioned during initialization of Arraylist(ArrayList<Integer>()) here E is Integer.

flow of control to increase size of an array in AL

Above diagram depicts the flow of control when we actually perform add operation using arraylist object.So as you can see there are series of method calls each responsible for checking the various constraint by having an lethal mechanism of exception handling to avoid given software to crash.This way of designing an software i feel is very intuitive.

So Arraylist basically grows 1 step at a time,by this i mean whenever your internal array gets filled up then arraylist will only increase size by one thereby not blocking huge size of memory but that includes cost of calling and accessing multiple time.But you can have an static version of arraylist ,if according to your requirement your need is to only have 500 size of array then you specify that too using :-

al.ensureCapacity(500);

Now your Arraylist can surely hold 500 elements without getting into so much method calls shown above.

So let me explain the above diagram what it does actually while increasing the size of an array.There is an private variable in ArrayList class i.e. size which works as top as in stack ,which has index of latest element added,so when we call add() method ,it will internally call ensureCapacityInternal() which inturn calls ensureExplicitCapacity() which has calculateCapacity function as parameter to the this function.

calculateCapacity checks if the array is newly made or it already has elements if it is new fresh array and the size mention is less then default size i.e. 10 then it would return minCapacity as 10 or otherwise it will return minCapacity as passed from above functions.

After these inside ensureExplicitCapacity we call grow() method which actually does the part of increasing the size of the array.It will compare two parameters that is minCapacity which it has got from super function and the size of the current array and it would increase size by 1 this is done as you must have guess by using System level method as shown below.

In terms of Performance: Arraylist takes O(n) times for inserting n elements as it need to access series of methods to check constraint related to memory and exception handling.

and other method like size(),isEmpty, get, set, iterator, and listIterator operations run in constant time O(1).

So guys,thats it from my end ,if you have any doubt please post it in comments below,i would love to help you :)🙋‍♂️