SortedSet and NavigableSet in Java

SortedSet in Java is an interface for sets that keep their elements in sorted order. NavigableSet extends SortedSet and adds methods for finding the closest elements, such as "the largest element less than or equal to 50". TreeSet is the main class that implements both. In this lesson, you will learn the methods of these two interfaces with examples.

Declaration

public interface SortedSet<E> extends Set<E>, SequencedSet<E>
public interface NavigableSet<E> extends SortedSet<E>

Methods of SortedSet

Methods of NavigableSet

Example: SortedSet Methods

Let's see an example of ranges in a sorted set of marks.

import java.util.SortedSet;
import java.util.TreeSet;
 
public class SortedDemo {
    public static void main(String[] args) {
        SortedSet<Integer> marks = new TreeSet<>();
        marks.add(50);
        marks.add(10);
        marks.add(40);
        marks.add(20);
        marks.add(30);
 
        System.out.println("All:     " + marks);
        System.out.println("First:   " + marks.first());
        System.out.println("Last:    " + marks.last());
        System.out.println("Below 30: " + marks.headSet(30));
        System.out.println("From 30:  " + marks.tailSet(30));
        System.out.println("20 to 40: " + marks.subSet(20, 40));
    }
}

All:     [10, 20, 30, 40, 50]
First:   10
Last:    50
Below 30: [10, 20]
From 30:  [30, 40, 50]
20 to 40: [20, 30]

Explanation: The numbers were added in mixed order but are stored sorted. headSet(30) excludes 30, tailSet(30) includes it, and subSet(20, 40) includes 20 but excludes 40.

Example: NavigableSet Methods

import java.util.NavigableSet;
import java.util.TreeSet;
 
public class NavigableDemo {
    public static void main(String[] args) {
        NavigableSet<Integer> s = new TreeSet<>(
            java.util.List.of(10, 20, 30, 40, 50));
 
        System.out.println("lower(30):   " + s.lower(30));
        System.out.println("floor(30):   " + s.floor(30));
        System.out.println("ceiling(30): " + s.ceiling(30));
        System.out.println("higher(30):  " + s.higher(30));
        System.out.println("floor(35):   " + s.floor(35));
        System.out.println("ceiling(35): " + s.ceiling(35));
        System.out.println("higher(50):  " + s.higher(50));
        System.out.println("descending:  " + s.descendingSet());
    }
}

lower(30):   20
floor(30):   30
ceiling(30): 30
higher(30):  40
floor(35):   30
ceiling(35): 40
higher(50):  null
descending:  [50, 40, 30, 20, 10]

Explanation: lower and higher never return the value itself; floor and ceiling do, if it exists. For 35, which isn't in the set, floor gives the nearest value below and ceiling the nearest value above. Nothing is higher than 50, so higher(50) returns null.

Common Mistakes

Unboxing the result of floor or ceiling into an int without checking. They return null when nothing matches.

Changing the original set while using a headSet view without realizing it's a live view. Changes show up in both.

Adding an element outside a subSet view's range. It throws IllegalArgumentException.

Practice

1. Easy: Store the bus times 7, 9, 12, 15 and 18 in a TreeSet and print the next bus after a given hour using ceiling.
2. Harder: Given grade boundaries 0, 40, 60, 75 and 90 in a NavigableSet, use floor to find the boundary for any score, then print the grade.

Key Takeaways