I need to iterate both forwards and backwards in a sorted set. If I use NavigableSet, I get a strictly-forward iterator and a strictly-backward iterator (iterator() and descendingIterator()) but none that can move forward and backward.
What's the time complexity of NavigableSet.lower() and higher() ? I can use those instead, but am reluctant to do so if they are inefficient.
There are only two implementations of the NavigableSet. Saying you opted for the TreeSet, while I don't have the source handy, the Javadoc says that it is based on a TreeMap providing O(log(n)) for get/put/containsKey/remove. At worst this would perform one get to find the value of we're finding the lower/higher for, plus an additional search to get the next/previous value, providing O(2log(n)) = O(log(n)).
Trees are worst case O(n) for search in the event it is actually a list, but in general, O(height).
Depending on your exact needs you could convert the sorted set to a list, say an array list, and use a list iterator for traversal. It can be used in both directions via the next() and previous() methods, which may be mixed freely.