List ​

In the collection classes, List is one of the most fundamental collections: it is an ordered list.

The behavior of List is almost identical to that of an array: elements are stored in the order they were added, and each element can be accessed by its index, starting from 0, just like arrays.

Arrays, similar to List, are also ordered structures. However, using arrays can be quite inconvenient when it comes to adding or removing elements. For example, if we want to remove the element at index 2 from an existing array {'A', 'B', 'C', 'D', 'E'}:

┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │
└───┴───┴───┴───┴───┴───┘
              │   │
          ┌───┘   │
          │   ┌───┘
          │   │
          ▼   ▼
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ D │ E │   │   │
└───┴───┴───┴───┴───┴───┘

This "delete" operation essentially requires shifting all elements after 'C' one position forward. Similarly, the "add" operation requires shifting elements after the specified position one position backward to make space for the new element. Implementing these operations with arrays is quite cumbersome.

Therefore, in practical applications where we need an ordered list with elements that can be added or removed, we primarily use ArrayList. In fact, ArrayList uses an array internally to store all its elements. For example, an ArrayList with 5 elements has an actual array size of 6 (leaving one empty space):

size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │   │
└───┴───┴───┴───┴───┴───┘

When adding an element at a specified index, ArrayList automatically shifts the necessary elements:

size=5
┌───┬───┬───┬───┬───┬───┐
│ A │ B │   │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘

Then, it adds the new element at the specified index and increments the size:

size=6
┌───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │
└───┴───┴───┴───┴───┴───┘

If more elements are added when the array is full, ArrayList first creates a larger new array, copies all elements from the old array, and then replaces the old array with the new one:

size=6
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Now that the new array has empty spaces, a new element can be added at the end, and the size increments:

size=7
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ A │ B │ F │ C │ D │ E │ G │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘

Thus, ArrayList encapsulates the add and remove operations, making it similar to array manipulation without worrying about how the internal elements are shifted.

Let's examine the List<E> interface, which contains several main methods:

• To add an element at the end: boolean add(E e)
• To add an element at a specified index: boolean add(int index, E e)
• To remove an element at a specified index: E remove(int index)
• To remove a specific element: boolean remove(Object e)
• To get an element at a specified index: E get(int index)
• To get the size of the list (number of elements): int size()

However, implementing the List interface isn't limited to arrays (i.e., the implementation of ArrayList). Another implementation, LinkedList, uses a "linked list" structure. In LinkedList, each internal element points to the next one:

        ┌───┬───┐   ┌───┬───┐   ┌───┬───┐   ┌───┬───┐
HEAD ──▶│ A │ ●─┼──▶│ B │ ●─┼──▶│ C │ ●─┼──▶│ D │   │
        └───┴───┘   └───┴───┘   └───┴───┘   └───┴───┘

Let's compare ArrayList and LinkedList:

Typically, we prefer to use ArrayList.

Characteristics of List ​

When using a List, we need to pay attention to the specifications of the List interface. The List interface allows us to add duplicate elements, meaning elements within a List can be repeated:

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

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple"); // size=1
        list.add("pear"); // size=2
        list.add("apple"); // allows duplicate elements, size=3
        System.out.println(list.size());
    }
}

The List also allows adding null:

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

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("apple"); // size=1
        list.add(null); // size=2
        list.add("pear"); // size=3
        String second = list.get(1); // null
        System.out.println(second);
    }
}

Creating a List ​

In addition to using ArrayList and LinkedList, we can also quickly create a List using the of() method provided by the List interface, based on given elements:

List<Integer> list = List.of(1, 2, 5);

However, the List.of() method does not accept null values. If null is passed, a NullPointerException will be thrown.

Traversing a List ​

Similar to array types, we can traverse a List using a for loop combined with the get(int) method:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = List.of("apple", "pear", "banana");
        for (int i = 0; i < list.size(); i++) {
            String s = list.get(i);
            System.out.println(s);
        }
    }
}

However, this approach is not recommended for two reasons: the code is more complex, and the get(int) method is efficient only for the ArrayList implementation. When switched to LinkedList, accessing elements by index becomes slower as the index increases.

Therefore, we should always use the Iterator to access a List. An Iterator is also an object created when the iterator() method is called on an instance of a List. The Iterator object knows how to traverse a List, and the implementation of the returned Iterator varies for different List types, but it always offers the highest access efficiency.

The Iterator object has two methods: boolean hasNext() checks if there is a next element, and E next() returns the next element. Thus, the code to traverse a List using an Iterator looks like this:

import java.util.Iterator;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = List.of("apple", "pear", "banana");
        for (Iterator<String> it = list.iterator(); it.hasNext(); ) {
            String s = it.next();
            System.out.println(s);
        }
    }
}

Some may feel that using an Iterator to access a List is more complicated than using an index. However, remember that traversing a List with an Iterator is always the most efficient method. Additionally, because Iterator traversal is so common, Java’s for-each loop can automatically use an Iterator for traversal. The code can be rewritten as follows:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = List.of("apple", "pear", "banana");
        for (String s : list) {
            System.out.println(s);
        }
    }
}

The above code represents the common way to traverse a List.

In fact, any collection class that implements the Iterable interface can be directly traversed using the for-each loop. The Java compiler itself does not know how to traverse collection objects, but it automatically converts the for-each loop into Iterator calls. This is because the Iterable interface defines an Iterator<E> iterator() method, which forces collection classes to return an Iterator instance.

Converting Between List and Array ​

There are three ways to convert a List to an Array. The first method is to call the toArray() method, which directly returns an Object[] array:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = List.of("apple", "pear", "banana");
        Object[] array = list.toArray();
        for (Object s : array) {
            System.out.println(s);
        }
    }
}

This method loses type information, so it is rarely used in practice.

The second method involves passing a type-matching array to toArray(T[]), which automatically copies the elements into the provided array:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = List.of(12, 34, 56);
        Integer[] array = list.toArray(new Integer[3]);
        for (Integer n : array) {
            System.out.println(n);
        }
    }
}

Notice that the generic parameter <T> of the toArray(T[]) method is not the same as the generic parameter <E> defined in the List interface. Therefore, we can actually pass an array of a different type; for example, passing a Number type array will still return a Number type array:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = List.of(12, 34, 56);
        Number[] array = list.toArray(new Number[3]);
        for (Number n : array) {
            System.out.println(n);
        }
    }
}

However, if we pass an array of an incompatible type, such as a String[] array, since the elements in the List are Integer, this will throw an ArrayStoreException.

What if the size of the passed array does not match the actual number of elements in the List? According to the List interface documentation:

If the provided array is not large enough, the List will create a new array that is just big enough to fit all the elements and return it. If the provided array is larger than the List's elements, the remaining elements will be filled with null.

In practice, it is most common to pass an array that is "exactly" the right size:

Integer[] array = list.toArray(new Integer[list.size()]);

The third, more concise way is to use the T[] toArray(IntFunction<T[]> generator) method defined in the List interface:

Integer[] array = list.toArray(Integer[]::new);

We will discuss this functional style further in later sections.

Converting Array to List ​

On the other hand, converting an Array to a List is much simpler. The easiest way is through the List.of(T...) method:

Integer[] array = { 1, 2, 3 };
List<Integer> list = List.of(array);

For versions prior to JDK 11, you can use the Arrays.asList(T...) method to convert an array to a List.

It is important to note that the returned List may not necessarily be an ArrayList or LinkedList, because List is just an interface. If we call List.of(), it returns a read-only List:

import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<Integer> list = List.of(12, 34, 56);
        list.add(999); // UnsupportedOperationException
    }
}

Calling add() or remove() methods on a read-only List will throw an UnsupportedOperationException.

Exercise ​

Given a series of consecutive integers, for example: 10, 11, 12, …, 20, but with one number missing, try to find the missing number:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Construct a sequence from start to end:
        final int start = 10;
        final int end = 20;
        List<Integer> list = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            list.add(i);
        }
        // Randomly remove one element from the List:
        int removed = list.remove((int) (Math.random() * list.size()));
        int found = findMissingNumber(start, end, list);
        System.out.println(list.toString());
        System.out.println("missing number: " + found);
        System.out.println(removed == found ? "Test Successful" : "Test Failed");
    }

    static int findMissingNumber(int start, int end, List<Integer> list) {
        return 0;
    }
}

Enhanced version: Similar to the above problem, but the integers are no longer ordered. Try to find the missing number:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Construct a sequence from start to end:
        final int start = 10;
        final int end = 20;
        List<Integer> list = new ArrayList<>();
        for (int i = start; i <= end; i++) {
            list.add(i);
        }
        // The shuffle algorithm can randomly swap the positions of elements in the List:
        Collections.shuffle(list);
        // Randomly remove one element from the List:
        int removed = list.remove((int) (Math.random() * list.size()));
        int found = findMissingNumber(start, end, list);
        System.out.println(list.toString());
        System.out.println("missing number: " + found);
        System.out.println(removed == found ? "Test Successful" : "Test Failed");
    }

    static int findMissingNumber(int start, int end, List<Integer> list) {
        return 0;
    }
}

Summary ​

A List is an ordered collection that can be accessed by index and has a variable length. Prefer using ArrayList over LinkedList.

You can directly use for-each to traverse a List.

Lists can be converted to and from Arrays.