--- title: Java ArrayList url: https://blog.octoperf.com/java-arraylist/ date: '2018-03-19' authors: - jloisel categories: - Development tags: - Java - Tutorial description: Java's ArrayList is a dynamic array implementation of the List interface. Learn how and when an ArrayList should be used. --- # Java ArrayList I guess you're here because you want to learn how to use the [ArrayList](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html) in your [Java](https://en.wikipedia.org/wiki/Java_(programming_language)) 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](https://fr.wikipedia.org/wiki/Thread_safety) for more information. Let's explore how to use an ArrayList through simple code examples! ## How Array List Works ![Dynamic Array](https://blog.octoperf.com/img/blog/java-arraylist/arraylist-structure.png) An `ArrayList` is based on the concept of [Dynamic Array](https://en.wikipedia.org/wiki/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](https://blog.octoperf.com/img/blog/java-arraylist/type-hierarchy.png) 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](https://docs.oracle.com/javase/tutorial/java/nutsandbolts/arrays.html) 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. ```java 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: ```java /** * 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](https://en.wikipedia.org/wiki/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](https://docs.oracle.com/javase/7/docs/api/java/util/Set.html) should be preferred in that case. (0(log n) because **Sets are sorted**, Lists are not) ## Constructors ```java 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 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: ```java @Test public void shouldCreate() { final List 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**: ```java /** * 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](https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html). It creates a copy of the passed collection: ```java @Test public void shouldCopy() { final List another = new ArrayList<>(); another.add("Hello World!"); final List 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. ```java @Test public void shouldAddElements() { final List 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] ```java @Test public void shouldAddStream() { final List 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](https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html) and [Lambdas expressions](https://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html). ## Removing Elements Removing elements is pretty straight forward: ```java @Test public void shouldRemoveElements() { final List 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 ```java @Test public void shouldIterate() { final List 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 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](https://docs.oracle.com/javase/8/docs/api/?java/lang/Iterable.html) 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](https://docs.oracle.com/javase/7/docs/api/java/util/Set.html). The complexity of this operation is `0(n)`. ```java @Test public void shouldSearch() { final List 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](https://en.wikipedia.org/wiki/Binary_search_algorithm). In this case, the complexity is `0(log n)`, which is much better than exhaustive search. ```java @Test public void shouldSearch() { final List 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](https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html): Doubly-linked list implementation, - [Vector](https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html): synchronized implementation based on a growable array of objects, - [Stack](https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html): specialization of a Vector with [LIFO](https://fr.wikipedia.org/wiki/Last_in%2C_first_out) 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.