NavigableSet Interface in Java – Guide with Examples
NavigableSet is a SortedSet with extra methods for moving around the sorted elements: finding the closest element below or above a value, taking ranges with the bounds you choose, walking backwards, and removing the smallest or largest element.
It was added to java.util in Java 6 and is implemented by TreeSet and ConcurrentSkipListSet. This tutorial covers every NavigableSet method with short, practical examples.
1. What Is a NavigableSet?
Imagine buying shoes. If size 8 is out of stock, the shop assistant checks the nearest sizes: "the biggest size below 8" or "the smallest size above 8". A NavigableSet answers exactly these questions in O(log n) time.
- All features of
SortedSet: sorted unique elements,first(),last()and range views. - Nearest-element lookups:
lower(),floor(),ceiling(),higher(). - Flexible ranges: choose whether each bound is inclusive.
- Reverse order:
descendingSet()anddescendingIterator(). - Retrieve and remove:
pollFirst()andpollLast().
2. Declaration and Hierarchy
public interface NavigableSet<E> extends SortedSet<E>Set
└─ SortedSet
└─ NavigableSet
├─ TreeSet (not thread-safe)
└─ ConcurrentSkipListSet (thread-safe)3. Finding the Nearest Element
The four lookup methods differ only in whether they include the value itself and in which direction they look. Each returns null when no element qualifies.
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;
public class NavigableLookups {
public static void main(String[] args) {
NavigableSet<Integer> sizes = new TreeSet<>(List.of(6, 7, 8, 9, 10, 11));
for (int wanted : new int[] {8, 12, 5}) {
System.out.printf("wanted=%-2d lower=%-4s floor=%-4s ceiling=%-4s higher=%s%n",
wanted, sizes.lower(wanted), sizes.floor(wanted),
sizes.ceiling(wanted), sizes.higher(wanted));
}
}
}wanted=8 lower=7 floor=8 ceiling=8 higher=9 wanted=12 lower=11 floor=11 ceiling=null higher=null wanted=5 lower=null floor=null ceiling=6 higher=6
| Method | Returns the… | Example with {6…11}, value 8 |
|---|---|---|
lower(e) | greatest element < e | 7 |
floor(e) | greatest element ≤ e | 8 |
ceiling(e) | smallest element ≥ e | 8 |
higher(e) | smallest element > e | 9 |
null when nothing matches. Assigning the result to an int variable unboxes it and throws NullPointerException; keep it as Integer and check for null.4. Range Views with Inclusive Bounds
SortedSet range views always include the lower bound and exclude the upper bound. NavigableSet adds overloads where you decide for each bound:
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;
public class NavigableRanges {
public static void main(String[] args) {
NavigableSet<Integer> ages = new TreeSet<>(List.of(12, 17, 18, 25, 40, 59, 60, 72));
System.out.println("Under 18: " + ages.headSet(18, false));
System.out.println("18 and under: " + ages.headSet(18, true));
System.out.println("Seniors (60+): " + ages.tailSet(60, true));
System.out.println("Adults 18 to 59: " + ages.subSet(18, true, 59, true));
System.out.println("Between 18 and 60: " + ages.subSet(18, false, 60, false));
}
}Under 18: [12, 17] 18 and under: [12, 17, 18] Seniors (60+): [60, 72] Adults 18 to 59: [18, 25, 40, 59] Between 18 and 60: [25, 40, 59]
Like all range views, these are backed by the original set: changes in one appear in the other.
5. Descending Order and Polling
descendingSet() returns a reverse-ordered view, and descendingIterator() walks from the largest element to the smallest. pollFirst() and pollLast() remove and return the ends, returning null on an empty set instead of throwing.
import java.util.Iterator;
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;
public class DescendingAndPoll {
public static void main(String[] args) {
NavigableSet<String> versions = new TreeSet<>(List.of("1.0", "1.2", "2.0", "2.1", "3.0"));
System.out.println("descendingSet(): " + versions.descendingSet());
System.out.print("descendingIterator(): ");
Iterator<String> it = versions.descendingIterator();
while (it.hasNext()) System.out.print(it.next() + " ");
System.out.println();
// pollFirst()/pollLast() remove as they return
System.out.println("pollLast(): " + versions.pollLast());
System.out.println("pollFirst(): " + versions.pollFirst());
System.out.println("Remaining: " + versions);
NavigableSet<String> empty = new TreeSet<>();
System.out.println("pollFirst() on empty set: " + empty.pollFirst());
}
}descendingSet(): [3.0, 2.1, 2.0, 1.2, 1.0] descendingIterator(): 3.0 2.1 2.0 1.2 1.0 pollLast(): 3.0 pollFirst(): 1.0 Remaining: [1.2, 2.0, 2.1] pollFirst() on empty set: null
Note that strings are compared character by character, so "10.0" would sort before "2.0". For real version numbers, use a comparator that compares the numeric parts.
6. Practical Example: Closest Value
Combining floor() and ceiling() finds the element nearest to any target, for example the nearest bus stop:
import java.util.List;
import java.util.NavigableSet;
import java.util.TreeSet;
public class ClosestValue {
// Returns the element closest to target (the smaller one on a tie)
static Integer closest(NavigableSet<Integer> set, int target) {
Integer below = set.floor(target);
Integer above = set.ceiling(target);
if (below == null) return above;
if (above == null) return below;
return (target - below <= above - target) ? below : above;
}
public static void main(String[] args) {
NavigableSet<Integer> busStops = new TreeSet<>(List.of(0, 450, 1200, 2000, 3100));
for (int position : new int[] {500, 1700, 2600, 5000}) {
System.out.println("At " + position + " m, nearest stop: " + closest(busStops, position) + " m");
}
}
}At 500 m, nearest stop: 450 m At 1700 m, nearest stop: 2000 m At 2600 m, nearest stop: 3100 m At 5000 m, nearest stop: 3100 m
7. All NavigableSet Methods
| Method | Description |
|---|---|
lower(e), floor(e), ceiling(e), higher(e) | Nearest element below or above e, or null. |
pollFirst(), pollLast() | Remove and return the lowest or highest element, or null if empty. |
descendingSet() | Reverse-order view of the set. |
descendingIterator() | Iterator from highest to lowest. |
headSet(to, inclusive) | View of elements below to (optionally including it). |
tailSet(from, inclusive) | View of elements above from (optionally including it). |
subSet(from, fromInc, to, toInc) | View of elements between two bounds. |
| Inherited from SortedSet | first(), last(), headSet(to), tailSet(from), subSet(from, to), comparator(). |
| Java 21 (sequenced) | getFirst(), getLast(), removeFirst(), removeLast(), reversed(). |
8. ConcurrentSkipListSet: A Thread-Safe NavigableSet
ConcurrentSkipListSet implements NavigableSet using a skip list, a layered linked structure that gives O(log n) operations and allows many threads to read and write at the same time without one big lock.
import java.util.NavigableSet;
import java.util.concurrent.ConcurrentSkipListSet;
public class ConcurrentSortedSet {
public static void main(String[] args) throws InterruptedException {
NavigableSet<Integer> ids = new ConcurrentSkipListSet<>();
Thread evens = new Thread(() -> { for (int i = 0; i < 1000; i += 2) ids.add(i); });
Thread odds = new Thread(() -> { for (int i = 1; i < 1000; i += 2) ids.add(i); });
evens.start(); odds.start();
evens.join(); odds.join();
System.out.println("size=" + ids.size() + ", first=" + ids.first() + ", last=" + ids.last());
System.out.println("ceiling(500)=" + ids.ceiling(500) + ", headSet(5)=" + ids.headSet(5));
}
}size=1000, first=0, last=999 ceiling(500)=500, headSet(5)=[0, 1, 2, 3, 4]
Its iterators are weakly consistent: they never throw ConcurrentModificationException. One caveat: size() walks the whole set, so it is O(n), not O(1).
9. NavigableSet vs SortedSet
| Feature | SortedSet | NavigableSet |
|---|---|---|
| Introduced in | JDK 1.2 | Java 6 |
| Nearest-element lookups | No | Yes |
| Range bounds | Fixed: lower inclusive, upper exclusive | Each bound configurable |
| Reverse view | reversed() (Java 21) | descendingSet() |
| Remove ends safely | No | pollFirst(), pollLast() |
10. Common Use Cases
- Nearest match: closest store, size, price or time slot.
- Ranges and bands: age groups, salary brackets, score grades.
- Leaderboards: top or bottom entries with
descendingSet(). - Simple ordered work lists: take the smallest item with
pollFirst()(aPriorityQueueallows duplicates, which a set does not). - Interval and calendar logic: find the event before or after a given time.
11. Summary
- NavigableSet extends SortedSet with navigation methods.
lower/floor/ceiling/higherfind the nearest element, returningnullif none exists.- Range methods accept inclusive flags for each bound.
descendingSet()gives a reverse view;pollFirst()andpollLast()remove the ends safely.- Implementations: TreeSet (single thread) and ConcurrentSkipListSet (concurrent).
Related Tutorials
Reference: Java SE 21 API: java.util.NavigableSet
Frequently Asked Questions (FAQ)
Q1. What is a NavigableSet in Java?
NavigableSet is an interface in java.util that extends SortedSet with navigation methods: nearest-element lookups, ranges with inclusive or exclusive bounds, descending views, and pollFirst()/pollLast().
Q2. Which classes implement NavigableSet?
TreeSet and ConcurrentSkipListSet. The keySet() of a TreeMap (through navigableKeySet()) is also a NavigableSet.
Q3. When was NavigableSet introduced?
In Java 6 (JDK 1.6), together with NavigableMap and ConcurrentSkipListSet.
Q4. What is the difference between floor() and ceiling()?
floor(e) returns the greatest element less than or equal to e; ceiling(e) returns the smallest element greater than or equal to e. If e is in the set, both return e.
Q5. What is the difference between lower() and floor()?
lower(e) excludes e and returns the greatest element strictly smaller. floor(e) includes e if it is present.
Q6. What do the navigation methods return when no element matches?
null. For example, higher() on the largest element returns null. Store the result in a wrapper type such as Integer, not int, to avoid a NullPointerException.
Q7. What is the difference between pollFirst() and first()?
first() returns the lowest element without removing it and throws NoSuchElementException on an empty set. pollFirst() removes and returns it, and returns null when the set is empty.
Q8. Is descendingSet() a copy?
No, it is a reverse-ordered view backed by the original set. Changes to either one are visible in the other. Calling descendingSet() on it again gives a view in the original order.
Q9. How do I include both ends in a range?
Use subSet(from, true, to, true). The headSet(to, true) and tailSet(from, true) overloads also let you choose whether the bound is included.
Q10. What is the time complexity of NavigableSet methods in a TreeSet?
lower, floor, ceiling, higher, pollFirst, pollLast, add, remove and contains are all O(log n). Creating a view is cheap; iterating it is proportional to the elements it contains.
Q11. Is NavigableSet thread-safe?
It depends on the implementation. TreeSet is not; ConcurrentSkipListSet is, and allows concurrent reads and writes without locking the whole set.
Q12. What is a skip list?
A sorted linked list with extra "express lane" levels that skip over many nodes at once. Searching starts on the top level and drops down, giving O(log n) average time. It is easier to make thread-safe than a balanced tree.
Q13. How do I find the element closest to a value?
Get floor(target) and ceiling(target), handle null for either, and return whichever is nearer, as shown in the bus stop example.
Q14. Can I use a NavigableSet as a priority queue?
Partly. pollFirst() removes the smallest element just like PriorityQueue.poll(), but a set cannot hold duplicates, so two tasks that compare as equal would collapse into one. Use a tie-breaker in the comparator or a real PriorityQueue.
Q15. Does NavigableSet allow null elements?
TreeSet with natural ordering and ConcurrentSkipListSet do not allow null. This is also why the navigation methods can safely use null to mean "no such element".
Q16. How do I iterate a NavigableSet in reverse?
for (Integer n : set.descendingSet()) { ... }
// or
Iterator<Integer> it = set.descendingIterator();Q17. Why declare a variable as NavigableSet instead of TreeSet?
It documents what your code needs (sorted navigation) without tying it to one class, so you can switch to ConcurrentSkipListSet later by changing one line.
Q18. What is the relation between NavigableSet and NavigableMap?
They mirror each other. NavigableMap has lowerKey(), floorKey(), ceilingKey() and higherKey(), and its navigableKeySet() returns a NavigableSet view of the keys.
Q19. Is size() fast on a ConcurrentSkipListSet?
No. Because the set can change while it is being counted, size() walks all elements, which is O(n), and the result may already be out of date. Use isEmpty() when you only need to know whether it has elements.
Q20. Do range views of a NavigableSet support navigation methods?
Yes. The views returned by the inclusive-bound overloads are themselves NavigableSets, so you can call floor(), pollFirst() or descendingSet() on them, limited to their range.