Data Structures - ArrayList

The ArrayList class is an array-based implementation of the List interface. Specifically, all elements of an ArrayList are stored in a Java array.

For example, an ArrayList named words has its underlying array of the size n. At this time, words are capable of storing at most n elements. We say the capacity of words is n elements. What will happen if we try to add n+1 elements to words? We will answer it after talking about common operations using ArrayList.

CRUD operations on an ArrayList

Let us write some example code using the ArrayList class. To use ArrayList, the concept of generic programming is needed. Simply speaking, you can think of generic programming as working with a general type T, where T can be replaced by any Java types such as int, float, String or even Object.

Please note that ArrayList and ArrayList<T> are different. The former is equivalent to ArrayList<Object>*. In the context of this article, ArrayList always refers to the latter generic version. Later in this series, we will learn more about generic programming.

As ArrayList was designed to be generic, you must specify the type of the elements that will be stored. For example, the declaration of an ArrayList named words whose elements are of type String is:

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

Since the words object is intended to be used as a List, it is advisable to declare words to be of type List <String>. Remember that although declared as List, the words object is still an ArrayList (to learn more, please read our tutorial on Polymorphism in Java).

List<String> words = new ArrayList<String>();

To append a String at the end of the words list

words.add("school"); // words is now ["school"]

Now, remember that the words can only hold elements of type String. If you try to add a double,

words.add(1.0);

The compiler should complain that:

The method add(String) in the type List<String> is not applicable for the arguments (double)

To insert a String at index 0

words.add(0, "at"); // words is now ["at", "school"]

To access an element via index

String w = words.get(0); // w is "at"

The available elements in words have their indexes in [0, 1, ..., words.size() - 1]. Accessing a non-existing element results in an java.lang.IndexOutOfBoundsException exception.

To update an element via index

words.set(1, "work"); // words is now ["at" , "work"]

To remove an element via index

words.remove(0); // words is now ["work"]

Here is a test class for the mentioned CRUD operations:

// File: ArrayListTest.java
import java.util.ArrayList;
import java.util.List;

public class ArrayListTest {
    public static void printList(List<String> words) {
        for (int i = 0; i < words.size(); i++) {
            System.out.println("Words[" + i + "]: " + words.get(i));
        }
    }

    public static void main(String []args) {
        List<String> words = new ArrayList<String>();
        // append
        words.add("school");
        printList(words);

        words.add(0, "at");
        System.out.println("> Insert via index");
        printList(words);

        words.set(1, "work");
        System.out.println("> Update via index");
        printList(words);

        words.remove(0);
        System.out.println("> Remove via index");
        printList(words);

    }
}

The above code produce:

Words[0]: school

> Insert via index

Words[0]: at

Words[1]: school

Update via index

Words[0]: at

Words[1]: work

Remove via index

Words[0]: work

Using List Iterator

Quite often, you care about iterating the elements of a List without bothering their indexes. In this usage scenario, it is recommended to use Iterator. As an implementation of the List interface, the ArrayList class provides a method to create an Iterator useful for iterating all elements of it.

Like the ArrayList class, the Iterator class uses generic programming. So, it is necessary to specify the type in the declaration. For example, the declaration for an Iterator over the words List of String: Iterator<String> iterator = words.iterator();

Let us write another version of the printList method using Iterator:

import java.util.Iterator;

public static void printList(List<String> words) {
   Iterator<String> iterator = words.iterator();

   while(iterator.hasNext()) {
     String word = iterator.next();
     System.out.print(word + " ");
   }

   System.out.println();
}

As you see, the Iterator class is simple, yet powerful. Since Java 1.5 (released in 2005), code using Iterator is occasionally shorten using the new for-loop. Here is how to rewrite the above method with Java's for:loop

public static void printList(List<String> words) {

   for(String word : words) {
      System.out.print(word + " ");
   }
   System.out.println();
}

Capacity of an ArrayList

In the beginning, we said that an ArrayList uses a fixed-size internal array to hold its elements. If all available space in the internal array has been used up and more space is needed, the ArrayList has no choice other than acquiring a bigger array, copy the old elements to the new array and use the new array in place of the old one.

How much space will be allocated for the new array?

Since Java 5.0, the size of the internal array doubles every time it needs more space. In short, trying to add just one element to an ArrayList which is full will result in costly operations:

(1) Acquiring a bigger array

(2) Copy all elements from the old array to the new array, If you know how much elements the ArrayList is intended to store, it is recommended to ensure the capacity - or the size of the internal array - before adding the elements.Grow this ArrayList instance, if necessary,to ensure that it can hold at least the number of elements specifiedby the minimum capacity argument.

void   ensureCapacity(int minCapacity);

Sometimes, the ArrayList no longer grows, and you want to save memory. The method trimToSize() can help you. Internally, a new array whose size is exactly the number of elements being stored will be allocated. Then, all elements are copied to this new array, freeing the space of the bigger old one.

// Shrink the capacity of this ArrayList instance to be the list's current size

void trimToSize();

Here is an example on how to store a really big number of elements without bearing the cost of allocating new internal array:

import java.util.ArrayList;

public class ArrayListCapacityTest {
   public static void main(String []args) {

       ArrayList<Integer> numbers = new ArrayList<Integer>();
       int SIZE = 1000000;
       numbers.ensureCapacity(SIZE);

       for (int i = 0; i < SIZE; i++) {
           numbers.add(i);
       }

      numbers.trimToSize();
      System.out.println("Number of elements is " + numbers.size());
   }
}

The above code produce:

Number of elements is 1000000

Summary

• The ArrayList class is an array-based generic implementation of the List interface.
• The class offers CRUD operations via index
• We can use Iterator or a for:loop to traverse an ArrayList.
• If we are going to store a big number of elements, use ensureCapacity to reserve spaces for them.