Ordering, Queues and Choosing a Collection

Collections hold things. Real programs also need to put them in order (the candidates with the highest scores first, the files sorted by name) and to process them in a particular order (the next task to run, the next request to handle). Both need an idea of what "comes before what", and both have a standard Java answer.

• How Comparable and Comparator define order, and how to chain comparators.
• Why a subtraction-based comparison is a bug.
• How sorted collections decide what a duplicate is.
• How Queue, Deque, ArrayDeque and PriorityQueue behave.
• How to choose a collection by its costs.

Numbers and strings know how to sort themselves. For your own classes, you teach Java what "natural order" means by implementing Comparable<T> and its single method compareTo. It returns a negative number if this object comes before the other, zero if they are equivalent in ordering, and a positive number if it comes after.

// File: Main.javaimport java.util.ArrayList;import java.util.Collections;import java.util.Comparator;import java.util.List;public class Main {    record Candidate(String name, int score, int yearsExperience) implements Comparable<Candidate> {        @Override        public int compareTo(Candidate other) {            return Integer.compare(other.score, this.score);   // natural order: highest score first        }    }    // The tempting but broken way to compare ints    static int brokenCompare(int a, int b) {        return a - b;    }    public static void main(String[] args) {        List<Candidate> list = new ArrayList<>(List.of(                new Candidate("Meena", 88, 2),                new Candidate("Asha", 92, 5),                new Candidate("Ravi", 88, 7),                new Candidate("Dev", 75, 1)));        Collections.sort(list);                                     // uses compareTo        System.out.println(list.stream().map(Candidate::name).toList());        // Comparator: orders defined outside the class, built from small pieces        list.sort(Comparator.comparingInt(Candidate::score).reversed()                .thenComparing(Candidate::yearsExperience, Comparator.reverseOrder())                .thenComparing(Candidate::name));        System.out.println(list.stream().map(Candidate::name).toList());        list.sort(Comparator.comparing(Candidate::name, String.CASE_INSENSITIVE_ORDER));        System.out.println(list.stream().map(Candidate::name).toList());        System.out.println(brokenCompare(Integer.MIN_VALUE, 1) > 0);       // wrong answer: overflow        System.out.println(Integer.compare(Integer.MIN_VALUE, 1) > 0);     // correct    }}

[Asha, Meena, Ravi, Dev][Asha, Ravi, Meena, Dev][Asha, Dev, Meena, Ravi]truefalse

Collections.sort(list) and list.sort(null) use the natural order. The Candidate record implements Comparable so that the natural order is "highest score first". When two candidates have the same score (Meena and Ravi, both 88), compareTo returns 0, and the sort is stable, meaning equal elements keep their original relative order, so Meena stays before Ravi.

The last two lines of output expose a bug that appears in a surprising amount of real code: a - b as a comparison. It looks like it works, but Integer.MIN_VALUE - 1 overflows and wraps around to a large positive number, so the sign is wrong and the sort silently misorders elements for extreme values. Always use Integer.compare(a, b) (or Comparator.comparingInt), which handles every case. This is overflow from article 2 striking again.

Like equals, compareTo has a contract: it must be antisymmetric (a.compareTo(b) and b.compareTo(a) have opposite signs), transitive, and consistent. It is strongly recommended to be consistent with equals: a.compareTo(b) == 0 should hold exactly when a.equals(b). Sorted collections use compareTo and not equals, so a mismatch produces surprising results, as we will see in a moment.

A class can have only one natural order, but you often need others: by name, by date, by score then name. A Comparator<T> is an object that compares two values, and it lives outside the class. The Comparator interface offers static factory methods that make comparators readable:

The chain in the example reads almost like English: "by score descending, then by years of experience descending, then by name". Beware one subtlety: comparingInt(Candidate::score).reversed() applies reversed() to that one comparator, and the thenComparing calls that follow are not reversed. Each step can be given its own direction, as with Comparator.reverseOrder() for the years.

The older style that you will meet in code from before Java 8 is an anonymous class:

Collections.sort(list, new Comparator<Candidate>() {    @Override    public int compare(Candidate a, Candidate b) {        return a.name().compareTo(b.name());    }});

It does the same job in five lines instead of one. Lambdas and method references (article 15) replaced this style.

TreeSet and TreeMap keep their elements sorted, using either the natural order or a comparator you give them. Crucially, they identify duplicates with the comparison, not with equals.

// File: Main.javaimport java.util.TreeMap;import java.util.TreeSet;public class Main {    public static void main(String[] args) {        TreeSet<String> names = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);        names.add("Asha");        names.add("asha");          // compares as equal to "Asha": treated as a duplicate        names.add("Ravi");        System.out.println(names + " size=" + names.size());        System.out.println(names.contains("RAVI"));        TreeMap<String, Integer> counts = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);        counts.merge("Java", 1, Integer::sum);        counts.merge("JAVA", 1, Integer::sum);        counts.merge("java", 1, Integer::sum);        System.out.println(counts);    }}

[Asha, Ravi] size=2true{Java=3}

With the case-insensitive comparator, "Asha" and "asha" compare as equal, so the set keeps only the first one, even though "Asha".equals("asha") is false. Sometimes that is exactly what you want (a case-insensitive map of words, as in the last line). When it is not, it is a source of vanishing data. The rule: the comparator defines equality for sorted collections, so make sure that it matches your intent, and include enough tie-breakers that elements that are different never compare as zero.

A queue holds elements for processing. The classic rule is first in, first out (FIFO): like a line at a counter, whoever has waited longest is served first. A Queue has two ways to do each operation, one that throws an exception on failure and one that returns a special value:

Prefer the offer, poll, peek family when an empty queue is a normal situation.

A Deque ("double-ended queue", pronounced "deck") allows insertion and removal at both ends, and so can act as a queue, a stack, or both. The recommended implementation is ArrayDeque: a resizable circular array. Its documentation says it is likely to be faster than Stack when used as a stack and faster than LinkedList when used as a queue. It does not allow null elements.

A stack is last in, first out (LIFO), like a pile of plates, with push and pop. Java has a legacy class java.util.Stack (it extends Vector, is synchronised and has all the List methods, which a stack should not have). The advice in the Java documentation itself is to use a Deque instead.

A PriorityQueue is different: it does not serve in arrival order, but always gives you the element that is smallest according to the natural order or a comparator. It is implemented as a binary heap, a tree stored in an array where each parent is no larger than its children. offer and poll cost logarithmic time, and peek is constant. Because only the smallest is guaranteed to be at the front, iterating over a PriorityQueue, or printing it, does not give sorted order. The documentation says explicitly that the iterator provides no guarantee about ordering.

// File: Main.javaimport java.util.ArrayDeque;import java.util.Comparator;import java.util.Deque;import java.util.List;import java.util.PriorityQueue;import java.util.Queue;public class Main {    record Task(String name, int priority) {}    static boolean balanced(String text) {              // a classic stack use        Deque<Character> stack = new ArrayDeque<>();        for (char c : text.toCharArray()) {            if (c == '(' || c == '[') {                stack.push(c);            } else if (c == ')' || c == ']') {                if (stack.isEmpty()) {                    return false;                }                char open = stack.pop();                if ((c == ')' && open != '(') || (c == ']' && open != '[')) {                    return false;                }            }        }        return stack.isEmpty();    }    public static void main(String[] args) {        Queue<String> line = new ArrayDeque<>();        line.offer("first");        line.offer("second");        line.offer("third");        System.out.println(line.poll() + " " + line.peek() + " " + line.size());        Deque<Integer> deque = new ArrayDeque<>();        deque.addFirst(2);        deque.addFirst(1);        deque.addLast(3);        System.out.println(deque + " " + deque.pollFirst() + " " + deque.pollLast());        System.out.println(balanced("(a[b])") + " " + balanced("(a[b)]") + " " + balanced("(("));        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority));        tasks.offer(new Task("write report", 3));        tasks.offer(new Task("fix outage", 1));        tasks.offer(new Task("reply to email", 5));        tasks.offer(new Task("review code", 2));        System.out.println("peek: " + tasks.peek().name());        StringBuilder order = new StringBuilder();        while (!tasks.isEmpty()) {            order.append(tasks.poll().name()).append("; ");        }        System.out.println(order);        // Top 3 largest values using a min-heap of size 3        PriorityQueue<Integer> top = new PriorityQueue<>();        for (int value : List.of(41, 7, 93, 18, 66, 25, 80)) {            top.offer(value);            if (top.size() > 3) {                top.poll();                             // discard the smallest of the four            }        }        System.out.println(top.stream().sorted().toList());    }}

first second 2[1, 2, 3] 1 3true false falsepeek: fix outagefix outage; review code; write report; reply to email;[66, 80, 93]

Notice how the pieces fit. The bracket checker uses an ArrayDeque as a stack: it pushes each opening bracket and pops it when the matching closing bracket arrives. The priority queue handed out the tasks by priority, regardless of insertion order. And the top-three example shows a small but powerful idea: to find the k largest values from a stream of any size, keep a min-heap of size k, and whenever it grows past k, throw away the smallest. It uses memory proportional to k, not to the size of the input.

Complexity lets you compare collections by operation. These are typical costs. Real performance also depends on constants, memory layout and data, so use them to choose a sensible default and measure when it matters.

In this table, "O(1)" means the cost does not grow with the collection's size, "O(log n)" grows slowly, and "O(n)" grows in proportion.

• Boxing. A List<Integer> stores references to Integer objects, not raw numbers. For millions of numbers, an int[] uses far less memory.
• Per-entry overhead. A HashMap entry is an object holding a key, a value, a hash and a link, on top of the key and value objects. A LinkedList node is an object with two links. An ArrayList has just a reference per element, plus spare capacity.
• Capacity. An ArrayList can have unused space. new ArrayList<>(expectedSize) avoids repeated growing when you know the size in advance, and trimToSize() releases the spare.

Ask three questions, in order:

1. Do I need key-value lookup? If yes, a Map. If not, a Collection.
2. What order do I need? None (hash-based), insertion (ArrayList, LinkedHash*), sorted (Tree*), priority (PriorityQueue), first-in-first-out or stack order (ArrayDeque).
3. Which operation will dominate? Index access favours ArrayList. Membership checks favour a hash set. Range and nearest-neighbour queries favour a tree.

If you are unsure, ArrayList, HashMap and HashSet are the right defaults. The rest are for specific needs, and the interface type you declare keeps your options open. Shared mutable collections between threads need special handling, covered in article 20.

• Comparing with subtraction.
• Forgetting thenComparing, so ties come out in arbitrary order.
• A comparator inconsistent with the intended equality in a TreeSet or TreeMap, causing items to disappear.
• Using Stack or Vector in new code.
• Calling remove() or element() on a queue that may be empty, and getting an exception.
• Assuming a PriorityQueue iterates in order.
• Putting null into an ArrayDeque (it throws).
• Choosing a collection by habit instead of by the operations needed.

Comparator<Employee> order = Comparator.comparing(Employee::department)        .thenComparing(Employee::salary, Comparator.reverseOrder())        .thenComparing(Employee::name);employees.sort(order);

static List<Integer> topK(Iterable<Integer> values, int k) {    PriorityQueue<Integer> heap = new PriorityQueue<>();    for (int value : values) {        heap.offer(value);        if (heap.size() > k) {            heap.poll();        }    }    List<Integer> result = new ArrayList<>(heap);    result.sort(Comparator.reverseOrder());    return result;}

• Next: Generics: Type Safety, Wildcards and Erasure explains the angle brackets used throughout this module.
• For comparators written as lambdas: Lambdas, Functional Interfaces and Method References.
• For sorting with streams: Streams in Practice (and When Not to Use Them).