Tech and Media Labs
This site uses cookies to improve the user experience.




Java Collections - NavigableSet

Jakob Jenkov
Last update: 2014-09-20

The java.util.NavigableSet interface is a subtype of the java.util.SortedSet interface. It behaves like a SortedSet with the exception you have navigation methods available in addition to the sorting mechanisms of the SortedSet. In this text I will look closer at some of these navigation methods.

In Java 6 there is only one implementation of the NavigableSet interface in the java.util package: java.util.TreeSet There is an implementation in the java.util.concurrent package but that is outside the scope of this trail.

Here is a list of the topics covered in this text:

  1. descendingIterator() and descendingSet()
  2. headSet(), tailSet() and subSet()
  3. ceiling(), floor(), higher() and lower()
  4. pollFirst() and pollLast()

descendingIterator() and descendingSet()

The first interesting navigation methods are the descendingIterator() and descendingSet() methods.

The descendingSet() method returns a NavigableSet in which the order of the elements is reversed compared to this one. The returned "view" is backed by the original NavigableSet, so changes to the descending set are also reflected in the original set.

Here is a simple example:

NavigableSet reverse = original.descendingSet();

The descendingIterator() method allows you to iterate the elements of the NavigableSet (which is also a SortedSet) in reverse order, without changing the order of the elements internally.

Iterator reverse = original.descendingIterator();    

headSet(), tailSet() and subSet()

The headSet() method returns a view of the original NavigableSet which only contains elements that are "less than" the given element. Here is an example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");

//this headset will contain "1" and "2"
SortedSet headset = original.headSet("3");

//this headset will contain "1", "2", and "3" because "inclusive"=true
NavigableSet headset = original.headSet("3", true);

The tailSet() method works the same way, except it returns all elements that are higher than the given parameter element.

The subSet() allows you to pass two parameters demarcating the boundaries of the view set to return. The elements matching the first boundary is included, where as elements matching the last boundary are not. Here is an example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");
original.add("4");
original.add("5");

//this subset will contain "2" and "3"
SortedSet    subset  = original.subSet("2", "4");

//this subset will contain "2", "3" and "4" because
//    fromInclusive=true, and toInclusive=true 
NavigableSet subset = original.subSet("2", true, "4", true);

ceiling(), floor(), higher(), and lower()

The ceiling() method returns the least (smallest) element in this set that is greater than or equal to the element passed as parameter to the ceiling() method. Here is an example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//ceiling will be "2".
Object ceiling = original.ceiling("2");

//floor will be "2".
Object floor = original.floor("2");

The floor() method does the opposite of ceiling()

The higher() method returns the least (smallest) element in this set that is greater than (not equal too) the element passed as parameter to the higher() method. Here is an example:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//higher will be "3".
Object higher = original.higher("2");

//lower will be "1"
Object lower = original.lower("2");

The lower() method does the opposite of the higher() method.


pollFirst() and pollLast()

The pollFirst() method returns and removes the "first" element in the NavigableSet or null if the set is empty. The pollLast() returns and removes the "last" element in the set or null if the set is empty. "First" means smallest element according to the sort order of the set. "Last" means largest according to teh element sorting order of the set.

Here are two examples:

NavigableSet original = new TreeSet();
original.add("1");
original.add("2");
original.add("3");


//first is "1"
Object first = original.pollFirst();

//last is "3"
Object last = original.pollLast();

Jakob Jenkov




Copyright  Jenkov Aps
Close TOC