The helpers

Every kitchen has a drawer full of gadgets. A peeler, a can opener, a whisk. You could peel a potato with a spoon, but why would you? Someone already made a tool for it, and it works.

Java has such a drawer for collections. Two classes are made entirely of ready-made tools.

• Collections (with an s, not to be confused with the word for the whole framework) works on lists, sets and maps: sorting, reversing, finding the biggest, searching, and wrapping a collection so that nobody can change it.
• Arrays does the same for plain arrays, the fixed rows that sit inside an ArrayList, such as int[].

Almost all of the tools work on a collection you already have. They are static methods, meaning you call them on the class itself, as in Collections.sort(list), rather than on an object you created.

The last third of this lesson covers a different kind of helper: ways to make a collection that cannot be changed, such as List.of. They are among the most useful and most misunderstood tools in Java.

Remember: before you write a loop to sort, copy, search or compare, check whether Collections or Arrays already has the method.

One of the best tools in the drawer is binary search. Suppose you want to find 60 in a row of numbers that is already sorted. You could start at the left and look at every number. Or you can look at the middle one first. It is 40, which is too small, so 60 can only be to its right, and the entire left half is out in one step. Look at the middle of what remains, and you hit 60 on the second look.

Every look throws away half of what is left. A row of a million items needs only about twenty looks, where checking one by one would need up to a million.

There is one condition, and it matters: the row must already be sorted. Run binary search on an unsorted row and it gives a meaningless answer, with no error to warn you.

Every block below can be pasted into jshell. Start with a tour of Collections.

List<Integer> scores = new ArrayList<>(List.of(40, 10, 30, 10, 50));
Collections.sort(scores);
System.out.println(scores);
Collections.reverse(scores);
System.out.println(scores);
System.out.println(Collections.max(scores));
System.out.println(Collections.min(scores));
System.out.println(Collections.frequency(scores, 10));
Collections.swap(scores, 0, 4); // swap the items at index 0 and index 4
System.out.println(scores);

[10, 10, 30, 40, 50]
[50, 40, 30, 10, 10]
50
10
2
[10, 40, 30, 10, 50]

sort puts the list in order and reverse flips it. max and min find the ends. frequency(list, 10) counts how many times 10 appears, and swap exchanges the items at two positions. All of them change or read the list you give them. To sort with your own rule, pass a Comparator from lesson 8.

Now binary search itself.

List<Integer> sorted = List.of(10, 20, 30, 40, 50, 60, 70, 80);
System.out.println(Collections.binarySearch(sorted, 60)); // found: its index
System.out.println(Collections.binarySearch(sorted, 25)); // missing: -(where it would go) - 1
System.out.println(Collections.binarySearch(sorted, 5));
System.out.println(Collections.binarySearch(sorted, 99));

5
-3
-1
-9

When the number is found, you get its index. When it is missing, you do not get plain -1. You get -(the place it would be inserted) - 1. For 25, the place would be index 2, so the answer is -2 - 1, which is -3. Any negative result means "not there", and you can recover the insertion point with -result - 1. Problem 1 uses exactly that trick.

Next, the same ideas for plain arrays.

int[] marks = {72, 91, 65, 80};
// Printing an array directly shows a code like [I@1b6d3586, so use Arrays.toString.
System.out.println(Arrays.toString(marks));
Arrays.sort(marks);
System.out.println(Arrays.toString(marks));
System.out.println(Arrays.binarySearch(marks, 80));
int[] bigger = Arrays.copyOf(marks, 6); // a longer copy, padded with zeros
System.out.println(Arrays.toString(bigger));
int[] middle = Arrays.copyOfRange(marks, 1, 3); // from index 1 up to, not including, 3
System.out.println(Arrays.toString(middle));
System.out.println(Arrays.equals(marks, new int[] {65, 72, 80, 91})); // same contents?
System.out.println(marks.equals(new int[] {65, 72, 80, 91})); // arrays keep the identity equals

[72, 91, 65, 80]
[65, 72, 80, 91]
2
[65, 72, 80, 91, 0, 0]
[72, 80]
true
false

• Arrays.toString is how you print an array. Printing an array directly shows a code like [I@1b6d3586, which is no use to anyone.
• Arrays.sort sorts the array in place, and Arrays.binarySearch searches it, with the same sorted-first rule.
• copyOf(array, 6) makes a new array of length 6. If that is longer, the extras are filled with zeros. copyOfRange(array, 1, 3) copies from index 1 up to but not including 3.
• Arrays.equals(a, b) compares contents. The plain a.equals(b) on arrays only asks "are these the same array?", so it says false for two separate arrays that look alike.

The bridge between the two worlds is Arrays.asList, which gives you a List for an array. It is easy to misuse, so look closely.

String[] seats = {"Asha", "Ravi", "Meera"};
List<String> view = Arrays.asList(seats); // a window onto the array, not a copy
view.set(0, "Kiran");
System.out.println(seats[0]); // the write went through to the array
seats[1] = "Zoya";
System.out.println(view.get(1)); // and the other way round
try {
    view.add("Dev"); // an array cannot grow, so neither can its window
} catch (UnsupportedOperationException e) {
    System.out.println("add refused");
}

Kiran
Zoya
add refused

The list is not a copy. It is a window onto the same array, so a change through either one shows in the other. You can set items, but you cannot add or remove, because an array has a fixed length.

int[] numbers = {1, 2, 3};
// asList wants objects. An int[] is one object, so you get a list of one array.
List<int[]> wrong = Arrays.asList(numbers);
System.out.println(wrong.size());
Integer[] boxed = {1, 2, 3};
System.out.println(Arrays.asList(boxed).size());

1
3

Here is the trap. asList works on objects, and an int[] is not an array of objects, so Java treats the whole int[] as one item and gives you a list of size 1. With an Integer[] it works as you would hope. If you have an int[], loop over it yourself.

Collections that cannot change

Sometimes you want to hand out a collection and be sure nobody changes it. Java has three ways, and they behave differently.

List<String> names = new ArrayList<>(List.of("Asha", "Ravi"));
List<String> view = Collections.unmodifiableList(names); // a read-only window
List<String> snapshot = List.copyOf(names);               // a frozen copy
names.add("Meera");
System.out.println(view.size());     // the window shows the change
System.out.println(snapshot.size()); // the copy does not
try {
    view.add("Kiran");
} catch (UnsupportedOperationException e) {
    System.out.println("view is read-only");
}
try {
    List.of("a", "b").add("c");
} catch (UnsupportedOperationException e) {
    System.out.println("List.of is read-only");
}

3
2
view is read-only
List.of is read-only

• Collections.unmodifiableList(list) is a read-only view, a window. The window refuses add, remove and set. But the real list behind it can still change, and the window shows the change. That is why view.size() printed 3.
• List.copyOf(list) is a snapshot, a frozen copy. It never changes and is not affected by what happens to the original, so it printed 2.
• List.of(...) builds a list that cannot be changed from the start. Set.of and Map.of do the same for sets and maps.

The of methods are strict about their input:

try {
    List.of("Asha", null); // List.of does not accept null
} catch (NullPointerException e) {
    System.out.println("List.of refuses null");
}
try {
    Set.of("Asha", "Asha"); // Set.of does not accept a repeat
} catch (IllegalArgumentException e) {
    System.out.println("Set.of refuses a repeat");
}

List.of refuses null
Set.of refuses a repeat

They never accept null, and Set.of and Map.of refuse repeated items or keys. The order that Set.of and Map.of give you when you loop over them is not promised either, so do not depend on it.

Remember: unmodifiableList is a read-only window onto a list that may still change. List.copyOf and List.of are frozen. Arrays.asList is a fixed-size window onto an array.

Binary search is short enough to write yourself, and it is a very popular interview task.

static int binarySearch(int[] sorted, int target) {
    int low = 0;
    int high = sorted.length - 1;
    while (low <= high) {
        int middle = (low + high) >>> 1; // >>> avoids overflow on a huge array
        if (sorted[middle] < target) {
            low = middle + 1; // everything up to middle is too small
        } else if (sorted[middle] > target) {
            high = middle - 1; // everything from middle on is too big
        } else {
            return middle;
        }
    }
    return -(low + 1); // low is where target would be inserted
}

Go through it in order.

• low and high mark the part of the array still in play. At the start, that is all of it.
• Each time round, look at middle. If it is too small, nothing at or before it can be the target, so low moves to middle + 1. If it is too big, high moves to middle - 1.
• When low passes high, nothing is left. At that moment low is exactly where the target would be inserted, which is why the library's answer is -(low) - 1. We write that as -(low + 1).
• The odd >>> 1 halves the sum. With very large arrays, low + high can overflow, and (low + high) / 2 would go wrong. The shift form is the safe way to write it. (>>> moves the bits right, which halves a non-negative number.)

int[] sorted = {10, 20, 30, 40, 50, 60, 70, 80};
System.out.println(binarySearch(sorted, 60));
System.out.println(binarySearch(sorted, 25));
System.out.println(binarySearch(sorted, 5));

5
-3
-1

The same answers as the library gave. Now the read-only view. It is a wrapper: a small object that holds the real list and passes reads through.

// A view holds the real list and passes reading through. It never copies.
static class ReadOnlyView<T> extends AbstractList<T> {
    private final List<T> inner;

    ReadOnlyView(List<T> inner) {
        this.inner = inner;
    }

    @Override
    public T get(int index) {
        return inner.get(index);
    }

    @Override
    public int size() {
        return inner.size();
    }
    // add, remove and set are not overridden, and AbstractList refuses them.
}

ReadOnlyView extends AbstractList, a class that builds a whole List out of just get and size. We implemented those two by asking the real list. We did not write add, set or remove, and AbstractList makes those throw UnsupportedOperationException. No copy is made, so the view is cheap, and it shows later changes.

List<String> names = new ArrayList<>(List.of("Asha", "Ravi"));
List<String> view = new ReadOnlyView<>(names);
names.add("Meera");
System.out.println(view);
try {
    view.add("Kiran");
} catch (UnsupportedOperationException e) {
    System.out.println("read-only");
}

[Asha, Ravi, Meera]
read-only

Meera was added to the real list afterwards, and the view shows her at once. This is exactly what Collections.unmodifiableList does, and the reason it is a window and not a freeze.

The cheap rows are cheap because they share. A view costs nothing to make and always shows the latest state. A copy costs O(n) to make and never changes. Choose by what you need to be true.

static void insertSorted(List<Integer> sorted, int value) {
    throw new UnsupportedOperationException("add value so the list stays sorted");
}

static void insertSorted(List<Integer> sorted, int value) {
    int index = Collections.binarySearch(sorted, value);
    if (index < 0) {
        index = -index - 1; // not found: turn the code back into the insertion point
    }
    sorted.add(index, value); // if it was found, a duplicate goes right beside it
}

static double median(int[] numbers) {
    throw new UnsupportedOperationException("the middle value of the numbers, once sorted");
}

static double median(int[] numbers) {
    if (numbers.length == 0) {
        throw new IllegalArgumentException("no numbers");
    }
    int[] copy = Arrays.copyOf(numbers, numbers.length); // never sort the caller's array
    Arrays.sort(copy);
    int middle = copy.length / 2;
    if (copy.length % 2 == 1) {
        return copy[middle];
    }
    return (copy[middle - 1] + copy[middle]) / 2.0; // two middles: their average
}

static class Roster {
    private final List<String> names = new ArrayList<>();

    void add(String name) {
        names.add(name);
    }

    // Bug: this hands out the real list, so any caller can change it.
    List<String> names() {
        return names;
    }
}

static class Roster {
    private final List<String> names = new ArrayList<>();

    void add(String name) {
        names.add(name);
    }

    List<String> names() {
        // A read-only window: callers can look, but not change.
        return Collections.unmodifiableList(names);
    }
}

• "Collection or Collections?" Collection is the interface at the top of the framework. Collections is a class of static helper methods. It is a classic trip-up, so say both out loud.
• "What does binarySearch return when the item is missing?" A negative number that equals -(insertion point) - 1. Add that the list must be sorted first, or the result is meaningless.
• "How would you implement binary search?" Problem-style answer: low, high, middle, and halve the range each loop. Mention >>> 1 or low + (high - low) / 2 to avoid overflow, which interviewers love.
• "Arrays.asList versus List.of?" asList is a fixed-size window onto an array: you can set, not add, and writes go through to the array. List.of is fully immutable and refuses null.
• "Is Collections.unmodifiableList immutable?" No. It is a read-only view. If someone holds the original list and changes it, the view changes too. For a real snapshot, use List.copyOf.
• "Why did my Arrays.asList(intArray) have one item?" An int[] is one object, not an array of objects. Use an Integer[], or loop.
• "How do you compare two arrays?" Arrays.equals for contents, Arrays.deepEquals for arrays inside arrays. Plain equals only checks identity.
• Say the cost. "Sort is O(n log n). Binary search is O(log n) on an array or ArrayList. Views are O(1) to make, copies are O(n)."

Made by VeraStack Labs