Difference between NavigableSet, SortedSet and TreeSet in Java

Question

• A TreeSet puts an element in natural ordering or by the provided comparator.
• A SortedSet is also keeps the element in natural order

But what is the difference between them and NavigableSet?
Where are NavigableSets useful?

Some example to show its usage would be nice for beginners.

Solution 1

SortedSet is an interface (it defines the functionality) and Treeset is an implementation. NavigableSet is also an interface subtype of the SortedSet.

You can't just write SortedSet<Integer> example = new SortedSet<Integer>();

You can however write SortedSet<Integer> example = new TreeSet<Integer>();

As its name implies, NavigableSets are more useful for navigating through the set.

http://mrbool.com/overview-on-navigableset-subtype-of-java-collections/25417 offers a good tutorial on NavigableSets and some of the methods available when using one, that aren't available in a SortedSet.

Solution 2

TreeSet implements NavigableSet, and (interface) NavigableSet extends SortedSet

Solution 3

I hope you will find useful the following excerpt from Java docs (see link to more details):

Methods lower, floor, ceiling, and higher return elements respectively less than, less than or equal, greater than or equal, and greater than a given element.

Solution 4

I feel this is a well demonstrated reference with decent explanation.

Solution 5

NavigableSet adds Navigation methods like descendingIterator() and descendingSet(), ceiling(), floor(), higher(), lower(), headSet(), tailSet(), subSet(), pollFirst() and pollLast().

View more solutions

Comments

[Bhesh Gurung]

check out the docs, the NavigaleSet provides direct methods to get to the elements at the various location of the set. TreeSet is an implementation.

[Hussain Akhtar Wahid 'Ghouri']

check this out : docs

[Stefan Reich]

The question is vaild because the all the implementations of SortedSet in the JDK also implement NavigableSet. So why does SortedSet exist as a separate interface? None of the answers here address this, and I am not aware of a data structure that would be able to implement SortedSet but not NavigableSet (although it may exist).

[Abdul]

Navigable set is extending SortedSet not implementing.