Java ArrayList

I guess you're here because you want to learn how to use the ArrayList in your Java code. You're in the right place!

As explained in the Java documentation, ArrayList is:

A resizable array: implementing the List interface,
Mutable: objects can be added and/or removed,
Not Thread-safe: ArrayList is not suitable for concurrent access. See Thread Safety for more information.

Let's explore how to use an ArrayList through simple code examples!

How Array List Works¶

Dynamic Array

Need professional services?

Rely on our Expertise

An ArrayList is based on the concept of Dynamic Array. (also known as growable, resizable array)

The array is grown as the number elements grows to always keep some space left for future insertions.

Type Hierarchy¶

Class Hierarchy inside JDK

The ArrayList inherits from:

java.util.AbstractList,
java.util.Object,
and implements java.util.List, java.util.Collection.

List is a subtype of Collection with guaranteed order of insertion.

Properties¶

The Java ArrayList has the following properties:

Can contain duplicate elements (i.e. elements which are equals),
Maintains the order of insertion,
is not synchronized (thus not thread-safe),
Random access (through an integer index) are fast (0(1)) because it's backed by an array,
Element removal is slow because elements must be shifted if any element is removed (to stay contiguous).

Methods¶

The following table lists ArrayList most commonly used methods:

Method	Description
void add(int index, Object element)	Inserts an element at a given index
boolean addAll(Collection c)	Appends all the elements contained in the passed collection
void clear()	Empties the list
int lastIndexOf(Object o)	Returns last index of given object, or -1 if not found
Object[] toArray()	Creates an array with a copy of all objects within the list
boolean add(Object o)	Appends the passed object to the list
boolean addAll(int index, Collection c)	Inserts all elements at the given index
Object clone()	Creates a shallow copy of the list (elements within are not cloned)
int indexOf(Object o)	Index of the object being passed, or -1 if not found
int size()	Number of elements the list contains

Comparison with Arrays¶

What makes an ArrayList very convenient is the fact it's a resizable array. Arrays is a primitive structure designed to hold a fixed number of objects. It's possible but quite difficult to resize an array (the code is usually pretty ugly too). For this reason, an ArrayList is much more convenient than an Array when you need to add/remove objects without knowing the exact collection size.

package com.octoperf;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class ArrayListTest {

  @Test
  public void shouldArray() {
    final String[] arr = new String[0];
    assertTrue(arr.length == 0);
  }
}

In the code above, we show how to create an empty array in Java. The code asserts the array length is zero. Now, let's see how the code differs when using an ArrayList.

Here is an extract from Java ArrayList source code:

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

As you can see, by default, an ArrayList is constructed with a capacity of 10 elements. Should you add more than 10 elements, the ArrayList is automatically resized to fit them. Wonderful isn't it?

Algorithmic Complexity¶

Before we dive into the code, let's see the most common operations this List performs algorithmically speaking. We're going to use the Big O-Notation to describe code complexity here.

Operation	Complexity
add(object o)	0(1)
add(object o, int index)	0(n)
remove(int index)	0(1)
remove(object o)	0(n)
size()	0(1)
contains(object o)	0(n)

Being based on an internal array, ArrayList is best suited for storing a limited number of elements (because increasingly growing and resizing hurts performance). Searching is not optimal, Sets should be preferred in that case. (0(log n) because Sets are sorted, Lists are not)

Constructors¶

package com.octoperf;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;

public class ArrayListTest {

  @Test
  public void shouldCreate() {
    final List<String> list = new ArrayList<>();
    assertTrue(list.isEmpty());
    assertFalse(list.iterator().hasNext());
  }
}

In the code above, we instantiate a new ArrayList, which is empty by default. Remember, it's designed to hold 10 elements by default. (and it will grow automatically if more than 10 are added)

You can also create an ArrayList with a default initial capacity:

  @Test
  public void shouldCreate() {
    final List<String> list = new ArrayList<>(50);
    assertTrue(list.isEmpty());
    assertFalse(list.iterator().hasNext());
  }

In the example above, the list has an internal array of capacity 50. The constructor argument is the internal array size. Beware of trying to optimize internal array size when instantiating a list. It's a common pitfall! Some developers tend to try to optimize the list size based on their guesses. It usually leads to overestimated list sizes consuming more memory. Or to underestimated list sizes leading to unusually high list internal array resizes.

Example: You create an ArrayList of size 1. You put 32 items in this list. It needs to grow to sizes: 2, 4, 8, 16 and 32. That's 5 resizes with full array copy! With default 10 size, it would have grown to: 20, 40. That's 2 resizes only.

Remember, the list resizes itself when the internal array capacity is not enough. Each time the capacity limit is reached, the size is grown by a factor of 1.5:

/**
 * 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);
}

int newCapacity = oldCapacity + (oldCapacity >> 1); is equivalent of multiplying the old capacity by 1.5. (1 bit shift to the right)

On each resize, all List elements are copied into a larger array.

You can also create a list by passing another Collection. It creates a copy of the passed collection:

@Test
public void shouldCopy() {
  final List<String> another = new ArrayList<>();
  another.add("Hello World!");

  final List<String> list = new ArrayList<>(another);
  assertFalse(list.isEmpty());
  assertTrue(list.contains("Hello World!"));

  another.clear();
  assertTrue(list.contains("Hello World!"));
}

The created List contains now contains a copy of all the elements the passed collection contains. Even if you clear the original collection, the element remains in the ArrayList.

Adding Elements¶

Elements can be added at the beginning, at the end one by one or multiples elements at once.

@Test
public void shouldAddElements() {
  final List<String> list = new ArrayList<>();
  list.add("John Smith");
  list.add("John Doe");
  list.add(0, "Donald Trump");
  list.addAll(ImmutableList.of("Barack Obama"));

  System.out.println(list);
}

The output is:

[Donald Trump, John Smith, John Doe, Barack Obama]

@Test
public void shouldAddStream() {
  final List<String> list = new ArrayList<>();

  ImmutableList.of("John Smith", "John Doe").forEach(list::add);

  System.out.println(list);
}

The output is:

[John Smith, John Doe]

The code above shows adding elements to the list using Java Streams and Lambdas expressions.

Removing Elements¶

Removing elements is pretty straight forward:

@Test
public void shouldRemoveElements() {
  final List<String> list = new ArrayList<>();
  list.add("John Smith");
  list.add("John Doe");

  list.remove("John Smith");

  System.out.println(list);
}

The following code prints:

[John Doe]

As with the add operations, multiple elements can be removed at once.

Iterating¶

@Test
public void shouldIterate() {
  final List<String> list = new ArrayList<>();
  list.add("John Smith");
  list.add("John Doe");

  // Foreach loop
  for (final String name : list) {
    System.out.println(name);
  }

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

  // Java Stream
  list.forEach(System.out::println);

  // Through iterator
  final Iterator<String> it = list.iterator();
  while (it.hasNext()) {
    System.out.println(it.next());
  }
}

The following code shows 4 different ways to iterate over list elements:

Foreach Loop: as List implements Iterable interface, lists can be iterated directly in for loops,
For Loop: traditional for loops using an integer index,
Java Streams: using Stream API introduced in Java 8,
Iterator: using list iterator.

These methods are roughly equivalent in term of performance. How you should iterate over the list depends on the context.

Searching¶

One should be aware that Lists are not very well suited for search operations, except for sorted lists.

Unsorted List¶

When searching an unsorted list, the algorithm is pretty inefficient: it scans the whole list to find the wanted element. If you need to perform frequent searchs in a collection, prefer a Set. The complexity of this operation is 0(n).

@Test
public void shouldSearch() {
  final List<String> list = new ArrayList<>();
  list.add("John Smith");
  list.add("John Doe");

  assertEquals(1, list.indexOf("John Doe"));
  assertTrue(list.stream().anyMatch("John Doe"::equals));
}

Sorted List¶

Sorted lists can be searched using binary search algorithm. In this case, the complexity is 0(log n), which is much better than exhaustive search.

@Test
public void shouldSearch() {
  final List<String> list = new ArrayList<>();
  list.add("John Smith");
  list.add("John Doe");

  Collections.sort(list);
  assertEquals(0, Collections.binarySearch(list, "John Doe"));
}

Best Use-Cases¶

ArrayList is best suited when:

Random Access: Seeking elements by index, the internal array allows a direct access to it,
Holding a constant number of elements: this way, you avoid any internal array resize (which is costly),
Evaluating List size: takes O(1).

ArrayList performs badly when:

Inserting / removing elements at specific index: the internal array must be grown / shrunk, and existing elements must be shifted,

Alternatives¶

ArrayList is not the only implementation of the Java List interface. In fact there is also:

LinkedList: Doubly-linked list implementation,
Vector: synchronized implementation based on a growable array of objects,
Stack: specialization of a Vector with LIFO strategy (Last In, First Out).

Depending on the nature of the operations frequently executed on the list instance, you should consider using one of these alternatives.

LinkedList is best suited for many add and remove operations: its doubly linked chain makes it easy to do so (simply reassigning pointers).

Vector is best suited in code executed concurrently by multiple threads because it's synchronized. This data structure is pretty old (since JDK 1.0) and not used much these days.

Stack is great when you need to pop elements in the reverse order they have been pushed.

Want to become a super load tester?

Request a Demo