ArrayList

The Problem

An array is an object that is used to store a fixed number of values of similar type. The length of an array is established when it is created. Once created its length can not be changed.

The problem with the array is that their length is fixed. Once full we cannot add any more elements to it. Let’s take an example –

String[] friends = new String[4];
friends[0] = "Bob";
friends[1] = "Sarah";
friends[2] = "Michael";
friends[3] = "Matt";

So, you have created an array of length 4 to hold your close friend’s name. And you have added their names into the array. Until this point everything is beautiful and little emotional.

Now if you want to add a new name into the array, what will happen?

friends[4] = "Lisa";

JVM will see there is no more space available to accommodate Lisa. So JVM will say sorry with following message: java.lang.ArrayIndexOutOfBoundsException: 4

So, how can I add “Lisa”? She is my real good friend.

Okay, Modify your array initialization to hold 5 elements:

String[] friends = new String[5];

So, do I always have to change the array length to add a new name?

That’s right. Or you can initialize your array with a huge length to avoid it. But it’s a real wastage of space.

Do I have any other option like an array with dynamic size?

Yes, of course. It’s called ArrayList.

The Solution

When you need an array with dynamic size, use ArrayList. An ArrayList grows its size automatically when new elements are added to it. Please remember –

1. ArrayList is a resizable Array. It can resize automatically when required.
2. ArrayList is internally backed by Array.
3. ArrayList can only store Objects, not primitives.
4. ArrayList allows duplicates.
5. ArrayList preserves the order of the elements in which they are inserted.
6. ArrayList’s methods are not synchronized. So the methods are not thread-safe.

How to create an ArrayList?

You can create an ArrayList object using three constructors –

We said, ArrayList is internally backed by Array. But as Array is a fixed length data structure, how does ArrayList work internally?

Let’s understand the concept with an example. Lets say, we are creating an ArrayList that will hold String Objects –

ArrayList<String> list = new ArrayList<String>();

Internally, it will create an  array of length 10 as shown below –

Object[] elementData = new Object[10];

When we try to add an item to this list, using add() method, the list first checks if the elementData (backing array) has room left to accommodate a new element. If there is room, the new item is just added at the next index. So, in our case, the first 10 elements will be added without any trouble.

If we try to add an eleventh element, the ArrayList will detect there is no room left for that element. So it will first create a larger array. Size of the new array may depend upon the Java version. Let’s assume the rule for new size is :  oldCapacity + old capacity/2. So, in our case, the new size would be: 10 + 10/2 = 15.

Now the old array will be copied into the new one. So, in the new Array, the first ten elements will be filled with ten elements of the old Array in exactly the same order.

Then, in the very next index, the eleventh element will be placed.

The method add(int index, E element) is used to add an element at a particular index. How does it work?

Let’s assume we have five elements: String1, String2, String3, String4 and String5 in our ArrayList.

Now if we try to add a String Hello into 2^nd index using add(2, "Hello") method, first String3, String4 and String5 will be shifted to the right.

Then the String Hello will be placed to the second index.

What is the difference between add(int index, E element) and set(int index, E element) method? Both look similar.

add(int index, E element) method inserts the specified element at the specified index.

set(int index, E element) method replaces the element at the specified index with the specified element.

Let’s assume we have five elements: String1, String2, String3, String4 and String5 in our ArrayList.

add(2, "Hello") will result: [String1, String2, Hello, String3, String4, String5]
set(2, "Hello") will result: [String1, String2, Hello, String4, String5]

We have said that ArrayList can hold only Objects. Then how does the below code don’t throw a compile time error?

ArrayList<Integer> integerList = new ArrayList<Integer>();
integerList.add(1); // Adding primitive

It might seem like we are trying to add a primitive data type in the ArrayList, but due to autoboxing, internally it will be converted first to an Integer object and then it will be added to the list.

When we say ArrayList can resize itself when required, does it mean it reduces its size automatically when elements are removed from it?

No. It doesn’t decrease its size automatically. But ArrayList provides a method trimToSize() to trim the size of this ArrayList instance to its current size.

How to iterate over an ArrayList?

There are three frequently used  approaches to traverse through the elements of an ArrayList. 

1. Using for loops.
2. Using for-each loop
3. Using Iterator

public class JavaDemo {
    public static void main(String[] args) {
        ArrayList<String> friends = new ArrayList<String>();
        friends.add("Bob");
        friends.add("Sarah");
        friends.add("Michael");
        friends.add("Matt");

        // 1. Using for loop
        for (int i = 0; i < friends.size(); i++) {
            System.out.println(friends.get(i));
        }

        // 2. Using for-each loop
        for (String friend : friends) {
            System.out.println(friend);
        }

        // 3. Using Iterator
        Iterator<String> iterator = friends.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

All the above three approach will give same output:

Bob
Sarah
Michael
Matt

Fail-fast Iterator

Let’s execute below code:

ArrayList<String> friends = new ArrayList<String>();
friends.add("Bob");
friends.add("Sarah");
friends.add("Michael");
friends.add("Matt");

for (String friend : friends) {
	friends.add("Lisa");
	System.out.println(friend);
}

Output:

Bob
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)

But why the exception?

All the implementations of Iterator in Collection classes including ArrayList are fail-fast except the concurrent collection classes like ConcurrentHashMap and CopyOnWriteArrayList.

Fail-fast Iterators fail as soon as they realize that the structure of the Collection has been modified by adding or removing elements since iteration has started.

During the first iteration we have added a new element and printed the first element from the original list. So, Bob is printed. Then during the second iteration the iterator realizes that the original collection is modified and throws the exception.

Other frequently used methods

That’s it for now. Hope you have got the idea of the ArrayList class.If you have any doubt, please ask in the comment section. I will try to answer that as soon as possible. Till then, bye bye.