Lists in practice

A list is easy to build and the work starts when it has to be sorted, cut or filtered. Four tools cover most of it: the two sort methods, the subList view, the Iterator that may remove while it walks, and removeIf. The trap in the middle is the one every Java programmer meets once: removing from a list inside a for-each loop.

Sorting a list

Collections.sort sorts a list in place by the natural order of its elements, which is the compareTo they inherit or implement. list.sort takes a comparator instead, and the lambda below reverses the order. binarySearch needs the sorted list and answers the index:

import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Sorted { public static void main(String[] args) { List<String> names = new ArrayList<>(List.of("pear", "apple", "fig")); Collections.sort(names); System.out.println(names); System.out.println(Collections.binarySearch(names, "fig")); names.sort((a, b) -> b.compareTo(a)); System.out.println(names); List<Integer> numbers = new ArrayList<>(List.of(5, 3, 9, 1)); Collections.sort(numbers); System.out.println(numbers); System.out.println(Collections.max(numbers) + " " + Collections.min(numbers)); } }

javac -Xlint:all Sorted.java
java Sorted

[apple, fig, pear]
1
[pear, fig, apple]
[1, 3, 5, 9]
9 1

fig is at index 1 of the sorted list, which is the answer of binarySearch to a list of three. The reverse sort puts pear first because the comparator asks for the greater element first, and the integers sort numerically through Integer.compareTo. A binarySearch of an unsorted list returns an index that means nothing, and the documentation says so.

subList is a view

subList(1, 4) does not copy: it returns a view of the positions from 1 up to but not including 4, and every change through the view is a change to the list. The program sets one element and then clears the view:

import java.util.ArrayList; import java.util.List; public class Sub { public static void main(String[] args) { List<String> list = new ArrayList<>(List.of("a", "b", "c", "d", "e")); List<String> middle = list.subList(1, 4); System.out.println(middle); middle.set(0, "B"); System.out.println(list); middle.clear(); System.out.println(list); } }

javac -Xlint:all Sub.java
java Sub

[b, c, d]
[a, B, c, d, e]
[a, e]

The first line is the view, the second shows the same change through the original list, and the third shows that clear on the view removed the three elements from the list. A view is the cheapest way to work on a range, and the most surprising if a reader assumes a copy; the copy is new ArrayList<>(list.subList(1, 4)).

Iterator and the concurrent modification

A for-each loop over a list uses an Iterator behind the scenes, and the iterator notices when the list changes behind its back. The program removes an even number inside the loop and the next call to the iterator throws:

import java.util.ArrayList; import java.util.Iterator; import java.util.List; public class Removing { public static void main(String[] args) { List<Integer> numbers = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6)); List<Integer> broken = new ArrayList<>(numbers); try { for (Integer n : broken) { if (n % 2 == 0) { broken.remove(n); } } } catch (java.util.ConcurrentModificationException e) { System.out.println("for-each: " + e.getClass().getSimpleName()); } Iterator<Integer> it = numbers.iterator(); while (it.hasNext()) { if (it.next() % 2 == 0) { it.remove(); } } System.out.println("iterator: " + numbers); List<Integer> third = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6)); third.removeIf(n -> n % 2 != 0); System.out.println("removeIf: " + third); } }

javac -Xlint:all Removing.java
java Removing

for-each: ConcurrentModificationException
iterator: [1, 3, 5]
removeIf: [2, 4, 6]

The exception is not about threads, although its name says concurrent: the iterator keeps a modification count, and a change through the list makes the count disagree. Its own remove updates both, which is why the second loop works. removeIf does the same internally and is the shortest of the three; its argument is a predicate, which is lesson 083.

removeIf

removeIf takes a predicate and removes every element for which it is true, in one pass, with no iterator in the source. It is the method to reach for whenever the condition is a one-line test, and the Iterator loop is what to write when the body has to do more than remove or when the removal depends on the previous element.

The predicate reads the element and answers a boolean, so n -> n % 2 != 0 keeps the even numbers by removing the odd ones. The name says what the code does, which the loop only shows to a reader who follows the braces.

ListIterator

A ListIterator can walk backwards, and it can replace the element it is standing on. The program starts at the end and prints backwards, then walks forward and upper-cases every element in place:

import java.util.ArrayList; import java.util.List; import java.util.ListIterator; public class Backwards { public static void main(String[] args) { List<String> list = new ArrayList<>(List.of("a", "b", "c")); ListIterator<String> it = list.listIterator(list.size()); while (it.hasPrevious()) { System.out.print(it.previous() + " "); } System.out.println(); ListIterator<String> forward = list.listIterator(); while (forward.hasNext()) { String value = forward.next(); forward.set(value.toUpperCase()); } System.out.println(list); } }

javac -Xlint:all Backwards.java
java Backwards

c b a
[A, B, C]

The first line ends with a space because the loop prints one after every element, which is why the println() follows it. listIterator(size) starts after the last element, so previous gives c first; a plain iterator() cannot go back at all, which is the whole reason the other class exists.

Exercises

  1. Sort a list of five numbers in reverse with list.sort and then search one with binarySearch.
  2. Copy the middle three elements of a five-element list into a new list and change the copy.
  3. Replace the Iterator loop of Removing with removeIf and compare the two outputs.
  4. Use a ListIterator to replace every element with its length in a list of strings.

Questions

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

  1. What does Collections.sort order a list by?

    Answer

    The natural order of the elements, from compareTo

    The method uses compareTo, so the element type must be Comparable or a comparator is needed.

  2. What is a subList?

    Answer

    A view of a range, so changes through it change the list

    The view has no storage of its own, which is why set and clear change the original.

  3. Why does removing inside a for-each loop throw?

    Answer

    The iterator notices the list changed outside it

    The iterator compares its modification count with the list and fails when they differ.

  4. What does this program print? import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Q1 { public static void main(String[] args) { List<Integer> list = new ArrayList<>(List.of(3, 1, 2)); Collections.sort(list); System.out.println(list); } }

    Answer

    [1, 2, 3]

    The sort orders the integers and changes the list in place.

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

    Answer

    [c, b, a]

    The comparator reverses the natural order, so the list is sorted downwards.

  6. What does this program print? import java.util.ArrayList; import java.util.List; public class Q3 { public static void main(String[] args) { List<String> list = new ArrayList<>(List.of("a", "b", "c", "d")); List<String> view = list.subList(1, 3); view.set(0, "B"); System.out.println(list); System.out.println(view.size()); } }

    Answer

    [a, B, c, d] then 2

    The view covers two elements and a change through it changes the list.

  7. What does this program print? import java.util.ArrayList; import java.util.List; public class Q4 { public static void main(String[] args) { try { List<Integer> list = new ArrayList<>(List.of(1, 2, 3)); for (Integer n : list) { list.remove(n); } } catch (java.util.ConcurrentModificationException e) { System.out.println("failed"); } } }

    Answer

    failed

    The first removal makes the iterator and the list disagree, and the next step throws.

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

    Answer

    [1, 2]

    The predicate selects the elements greater than two, and removeIf removes them.

  9. What can a ListIterator do that an Iterator cannot?

    Answer

    Walk backwards and replace the current element

    Both can read and remove, and only ListIterator has previous and set.

  10. What does binarySearch require of the list?

    Answer

    That it is sorted the same way the search assumes

    The search halves the range by comparison, so an unsorted list gives a meaningless index.

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

Banner image