List and ArrayList

A List is an ordered collection with a position for every element, and ArrayList is its usual implementation: an array that grows. The interface is what the code should name, and the implementation is a decision about cost that the program makes once. This lesson walks the methods, reads the two meanings of remove, shows the lists that cannot grow, and measures the two implementations against each other.

A List and its methods

The program adds three names, reads one by position, replaces one, asks for the position of a value and removes two:

import java.util.ArrayList; import java.util.List; public class Lists { public static void main(String[] args) { List<String> names = new ArrayList<>(); names.add("Ada"); names.add("Grace"); names.add("Edsger"); System.out.println(names); System.out.println(names.size() + " " + names.get(1)); names.set(2, "Dijkstra"); System.out.println(names); System.out.println(names.contains("Grace") + " " + names.indexOf("Grace")); names.remove("Ada"); System.out.println(names); names.remove(0); System.out.println(names); } }

javac -Xlint:all Lists.java
java Lists

[Ada, Grace, Edsger]
3 Grace
[Ada, Grace, Dijkstra]
true 1
[Grace, Dijkstra]
[Dijkstra]

toString of a list prints the elements in order, separated by commas and inside brackets, which is a convenience the JDK documents. set replaces and returns the old value, indexOf answers -1 for a value that is not there, and a list is equal to another list with the same elements in the same order.

remove by value and by index

List has two remove methods: remove(int index) and remove(Object value). Which one a call means depends on the type of the argument, and for a List<Integer> the two are easy to confuse: remove(1) removes the element at position 1 and remove(Integer.valueOf(1)) removes the value 1, wherever it is.

The program above removes a String by value and then the element at position 0, and the two lines of output show which is which. The compiler chooses the overload from the static type of the argument, so an int always means the index, even inside a list of numbers.

Fixed-size and immutable lists

Two factory methods return lists that are real List objects and refuse to change size. Arrays.asList wraps an array, so set works and add fails; List.of is immutable, so both fail. The program catches the two exceptions and prints their class:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Fixed { public static void main(String[] args) { List<String> fromArray = Arrays.asList("a", "b"); System.out.println(fromArray); List<String> immutable = List.of("x", "y"); System.out.println(immutable); try { fromArray.add("c"); } catch (UnsupportedOperationException e) { System.out.println("asList add: " + e.getClass().getSimpleName()); } try { immutable.set(0, "z"); } catch (UnsupportedOperationException e) { System.out.println("List.of set: " + e.getClass().getSimpleName()); } List<String> growable = new ArrayList<>(fromArray); growable.add("c"); System.out.println(growable); } }

javac -Xlint:all Fixed.java
java Fixed

[a, b]
[x, y]
asList add: UnsupportedOperationException
List.of set: UnsupportedOperationException
[a, b, c]

The last three lines are the usual fix: pass the fixed list to the ArrayList constructor and change the copy, so the original stays as it was. A List.of is the right type for a constant, because it cannot be changed by accident and the caller may keep a reference to it for ever.

ArrayList against LinkedList

ArrayList holds an array and grows it by copying, so get by index is one array access and add at the end is amortised constant time. Adding at position 0 moves every element, which is linear. A LinkedList is a chain of nodes, so adding at either end is constant time and reading position i walks i nodes.

Both are List, so the same code uses either; the difference is the cost of the operations the code performs. The measurement below is one run in this container, with twenty thousand elements:

import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Timing { public static void main(String[] args) { int n = 20_000; System.out.println("add at index 0, n = " + n); long[] array = measure(new ArrayList<>(), n); long[] linked = measure(new LinkedList<>(), n); System.out.printf("ArrayList %d ms%n", array[0]); System.out.printf("LinkedList %d ms%n", linked[0]); long[] arrayGet = measureGet(new ArrayList<>(), n); long[] linkedGet = measureGet(new LinkedList<>(), n); System.out.printf("get in the middle: ArrayList %d ms, LinkedList %d ms%n", arrayGet[0], linkedGet[0]); } static long[] measure(List<Integer> list, int n) { long start = System.nanoTime(); for (int i = 0; i < n; i++) { list.add(0, i); } return new long[] {(System.nanoTime() - start) / 1_000_000}; } static long[] measureGet(List<Integer> list, int n) { for (int i = 0; i < n; i++) { list.add(i); } long start = System.nanoTime(); int sum = 0; for (int i = 0; i < 20_000; i++) { sum += list.get(n / 2); } long ms = (System.nanoTime() - start) / 1_000_000; if (sum == 42) { System.out.println(sum); } return new long[] {ms}; } }

javac -Xlint:all Timing.java
java Timing

add at index 0, n = 20000
ArrayList 33 ms
LinkedList 16 ms
get in the middle: ArrayList 2 ms, LinkedList 622 ms

Measured here

The first pair is closer than the textbook suggests: adding at 0 is linear for ArrayList and constant for LinkedList, but the linear part is a memory move of a few hundred kilobytes, which the processor does quickly, while the linked list allocates a node per element and chases pointers. The second pair is the one to remember: twenty thousand reads in the middle cost 2 ms against 622 ms, a factor of about 300, because one index access became a walk of ten thousand nodes.

Numbers like these depend on the machine, the JDK and the run, so treat them as one sample and measure your own before a decision. The conclusion that survives is the shape: ArrayList wins on reading by index and at the end, LinkedList wins on adding and removing at the ends, and code that reads by index should not use a linked list at all. In practice ArrayList is the default, and ArrayDeque of lesson 074 is the better queue when the ends are what matters.

Exercises

  1. Make a List<Integer> of 1, 2 and 3 and remove the value 1 with remove(Integer.valueOf(1)), then compare it with remove(1).
  2. Add a fourth name to Lists.java at position 1 and print the list.
  3. Time add at the end for both lists and explain the result.
  4. Pass the list from List.of to an ArrayList and change it, then print both.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. Which method reads an element by position?

    Answer

    get

    List.get takes the index and returns the element, and throws for an index out of range.

  2. What does remove(1) mean on a List<Integer>?

    Answer

    Remove the element at position 1

    An int argument selects the index overload, whatever the element type is.

  3. What does List.of return?

    Answer

    An immutable list that refuses add and set

    The list of List.of cannot be changed in any way once it is built.

  4. What does this program print? import java.util.ArrayList; import java.util.List; public class Q1 { public static void main(String[] args) { List<String> list = new ArrayList<>(); list.add("a"); list.add("b"); list.set(0, "c"); System.out.println(list); } }

    Answer

    [c, b]

    set replaces the element at position zero, so c takes the place of a.

  5. What does this program print? import java.util.ArrayList; import java.util.List; public class Q2 { public static void main(String[] args) { List<String> list = new ArrayList<>(List.of("a", "b", "a")); System.out.println(list.indexOf("a")); System.out.println(list.lastIndexOf("a")); System.out.println(list.contains("c")); } }

    Answer

    0 then 2 then false

    indexOf finds the first a, lastIndexOf the last, and c is not in the list.

  6. What does this program print? import java.util.ArrayList; import java.util.List; public class Q3 { public static void main(String[] args) { List<Integer> list = new ArrayList<>(List.of(10, 20, 30)); list.remove(1); System.out.println(list); } }

    Answer

    [10, 30]

    The int argument is the index, so the element at position one is removed.

  7. What does this program print? import java.util.Arrays; import java.util.List; public class Q4 { public static void main(String[] args) { List<String> list = Arrays.asList("a", "b"); try { list.add("c"); } catch (UnsupportedOperationException e) { System.out.println("refused"); } } }

    Answer

    refused

    asList wraps a fixed-size array, so the add throws and the catch prints.

  8. What does this program print? import java.util.ArrayList; import java.util.LinkedList; import java.util.List; public class Q5 { public static void main(String[] args) { List<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(0, 0); System.out.println(list); System.out.println(list.get(2)); } }

    Answer

    [0, 1, 2] then 2

    Adding at index zero puts the element first, and get(2) reads the last.

  9. Why is reading by index slow on a LinkedList?

    Answer

    It walks the chain of nodes to reach the position

    A linked list has no array to index into, so a read is a walk.

  10. What is the usual fix for a fixed-size list that must grow?

    Answer

    Copy it into a new ArrayList and change the copy

    The copy is growable, and the fixed list stays as it was for its other readers.

The code on this page was built with OpenJDK 21.0.13 (javac and java) and run on Alpine Linux in a Docker container.

Article author: Arthur Isaev