Java: SortedSet "cursor"-style iterator

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.

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.

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).