List and ArrayList

Use List for ordered data with duplicates, know what ArrayList operations cost, and avoid the remove(int) trap and linear lookups.

SyntaxList<String> names = new ArrayList<>(); names.add("ada"); // append names.add(0, "linus"); // insert at index String first = names.get(0); names.set(1, "grace"); names.remove("grace"); // by value; remove(0) is by index

A List is an ordered sequence. Every element has an index starting at 0, duplicates are allowed, and iteration follows insertion order. It is the type you use for query results, JSON arrays and anything a client will page through.

How ArrayList works

ArrayList is the default implementation. It keeps elements in an internal array and grows it, by about half its size, when it fills up. That explains its costs:

  • get(i) and set(i, x) are constant time.
  • add(x) at the end is constant time on average, with an occasional copy when the array grows.
  • add(i, x) and remove(i) near the front shift every later element.
  • contains and indexOf scan the list and call equals on each element.

When you know the size up front, such as mapping 500 database rows to records, new ArrayList<>(rows.size()) avoids the growth copies. LinkedList is rarely faster in practice: it spends memory on a node per element and walks nodes for every index lookup.

Equality

Two lists are equal when they have the same elements in the same order, whatever their classes, so an ArrayList can equal a List.of. contains, indexOf and remove(Object) all depend on the elements' equals. Records get a correct one for free; a plain class without it is only ever equal to itself.

Mistakes people make

  • remove(int) versus remove(Object). On a List<Integer>, ids.remove(2) removes the element at index 2, not the value 2. Write ids.remove(Integer.valueOf(2)) to remove by value.
  • Lookups in a loop. Calling list.contains for every item of another list is quadratic. For 10,000 by 10,000 items that is up to 100 million comparisons; put one side in a HashSet.
  • subList is a view. It shares storage with the original list. Changing the original's size afterwards makes the view throw ConcurrentModificationException, so copy it with List.copyOf before you keep or return it.
  • Index errors. get(size()) throws IndexOutOfBoundsException. Check bounds when an index comes from a request parameter.

Back-end angle

Paginate in the database with LIMIT and OFFSET or a keyset when you can. Slicing a list in memory is fine for a small, already loaded result, such as a cached list of countries.

Example

Try it yourself
Loading editor…
Press Run to execute the code.

When to use it

  • Map the rows of a SELECT into a pre-sized ArrayList of records before returning them from a repository.
  • Hold the ordered line items of an order so the receipt prints them in the order they were added.
  • Slice a small cached list of countries into pages for a dropdown endpoint.

More examples

remove(int) versus remove(Object)

Overload resolution prefers remove(int) because it needs no boxing. This bug usually shows up when a list of numeric ids loses the wrong row.

Example · java
void main() {
    List<Integer> ids = new ArrayList<>(List.of(10, 20, 30, 2));

    ids.remove(2);                        // index 2: removes 30
    IO.println("after remove(2): " + ids);

    ids.remove(Integer.valueOf(2));       // the value 2
    IO.println("after remove(Integer.valueOf(2)): " + ids);
}
// Output:
// after remove(2): [10, 20, 2]
// after remove(Integer.valueOf(2)): [10, 20]

Pre-sized mapping and in-memory pages

Rejecting negative values from the request and clamping both bounds means a page past the end returns an empty list instead of throwing. Copying the subList detaches the page from the source list.

Example · java
record User(int id, String name) {}

List<User> page(List<User> users, int page, int size) {
    if (page < 0 || size < 1) {
        throw new IllegalArgumentException("page must be >= 0 and size >= 1");
    }
    int from = (int) Math.min((long) page * size, users.size());
    int to = Math.min(from + size, users.size());
    return List.copyOf(users.subList(from, to));   // copy, do not keep the view
}

void main() {
    List<String> names = List.of("ada", "linus", "grace", "ken", "barbara");

    List<User> users = new ArrayList<>(names.size());
    for (int i = 0; i < names.size(); i++) {
        users.add(new User(i + 1, names.get(i)));
    }

    for (int p = 0; p < 4; p++) {
        List<String> slice = page(users, p, 2).stream().map(User::name).toList();
        IO.println("page " + p + ": " + slice);
    }
}
// Output:
// page 0: [ada, linus]
// page 1: [grace, ken]
// page 2: [barbara]
// page 3: []

Equality across list types

List equality compares elements in order, so an ArrayList equals a List.of with the same records, and the same elements in another order do not. replaceAll rewrites every element in place.

Example · java
record Item(String sku, int qty) {}

void main() {
    List<Item> cart = new ArrayList<>(List.of(new Item("A-1", 2), new Item("B-7", 1)));
    IO.println("contains B-7 x1: " + cart.contains(new Item("B-7", 1)));

    List<Item> expected = List.of(new Item("A-1", 2), new Item("B-7", 1));
    IO.println("equals before sort: " + cart.equals(expected));

    cart.sort(Comparator.comparing(Item::sku).reversed());
    IO.println("equals after sort: " + cart.equals(expected));

    cart.replaceAll(item -> new Item(item.sku(), item.qty() * 10));
    IO.println(cart);
}
// Output:
// contains B-7 x1: true
// equals before sort: true
// equals after sort: false
// [Item[sku=B-7, qty=10], Item[sku=A-1, qty=20]]

Related

java the collections frameworkjava set and hashsetjava immutable collectionslist addlist remove

Discussion

  • Be the first to comment on this lesson.