Overview

ArrayList is a resizable array implementation of the List interface i.e. ArrayList grows dynamically as the elements are added to it.

If the size of the current elements (including the new element to be added to the ArrayList) is greater than the maximum size of the array then increase the size of array. But the size of the array can not be increased dynamically. So, what happens internally is, a new Array is created and the old array is copied into the new array.

Let’s see how ArrayList is internally implemented; what is the backing data structure for an ArrayList, how it grows dynamically.

How ArrayList grows dynamically?
How ArrayList grows dynamically?

ArrayList implementation in Java

Internally an ArrayList uses an Object[] Array. All the addition, removal and traversal happens on this array.

In Java 7 or previous

In Java 8 or later

As observed, in Java 8 private keyword is removed to provide access to nested class i.e. Itr, ListItr, SubList

Empty List initialization with default capacity

When an object of ArrayList is created without initial capacity, the default constructor of the ArrayList class is invoked. It uses empty array instance to create the new object.

the following code is executed:

In Java 7 or previous

Here, default capacity of 10 is assigned at a time of empty initialization of ArrayList

In Java 8 or later

Here, empty list is inialized with default capacity of 10; ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY when the first element is added.

Empty List initialization with initial capacity

When an object of ArrayList is created with an initial capacity, the ArrayList constructor is invoked to create the array internally.

and the following code is executed:

In Java 7 or previous

Here, the size of the array will be equal to the argument passed in the constructor.

In Java 8 or later

Here, the size of the array will be equal to the argument passed in the constructor. Then, size of the array will be 30 in above example.

Non empty list containing the elements of a specified collection

An object of ArrayList also can be created based on a specific collection.

then the following code is executed:

The above ArrayList constructor will create an non empty list containing the elements of the collection passed in the constructor.

How the size of ArrayList grows dynamically?

In the add(Object), the capacity of the ArrayList will be checked before adding a new element. Here is the implementation of the add() method.

As elements are added to an ArrayList, its capacity grows automatically.

In Java 6 or previous

Consider an ArrayList, , with capacity . Once ‘s underlying array is filled to capacity with values, a new underlying array is created that has increased capacity. The elements currently stored in are then copied over to the new, larger capacity array, and the new array replaces ‘s original underlying array. Typically, the increased capacity is some manner of rough doubling though the actual amount that the capacity increases depends on the implementation of ArrayList you’re using. In some Java implementations, the ensureCapacity method in ArrayList class ensure the new size of the underlying array:

int newCapacity = (oldCapacity * 3)/2 + 1;

Increasing the capacity by what amounts to 1.5X is still enough to give some guarantees:O(1) access and O(1) insertion (on average). This has the advantage of wasting slightly less space when the ArrayList is not very full.

In Java 7 or later

ensureCapacityInternal() determines what is the current size of occupied elements and what is the maximum size of the array.

The grow method in ArrayList class ensure the new size of the underlying array:

int newCapacity = oldCapacity + (oldCapacity >> 1);

In the above code, minCapacity is the size of the current elements (including the new element to be added to the ArrayList).

Performance of ArrayList

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time.

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

It's good to share...Share on FacebookTweet about this on TwitterShare on LinkedInPin on PinterestShare on Google+Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *