How to make a sorted set with an O(1) random access by index

Question

Need a collection of strings where elements inserted needed to be sorted and also non-duplicate, can be retrieved through index.

• I can use TreeSet which removes duplicates and sorts everything in order but cannot retrieve through index. for retrieving through index, i can make ArrayList and addAll elements to it, but this addAll takes lot of time.

or

• I can use an ArrayList, insert required and then remove duplicates by some other method, then using Collections.sort method to sort elements.

But the thing is, all these take time, is there any straight-way to achieve this, a collection -sorted, non-duplicate, with O(1) random access by index.

Answer 1

There's a Data Type in the commons collection called SetUniqueList that I believe meetsyour needs perfectly. Check it out:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html

Answer 2

You can use the second idea:

I can use ArrayList,insert required and then remove duplicates by some other method, then using Collections.sort method to sort elements.

but instead of removing the duplicates before the sort, you could sort the ArrayList first, then all duplicates are on consecutive positions and can be removed in a single pass afterwards.

At this point, both your methods have the same overall complexity: O(N*logN) and it's worth noting that you cannot obtain a sorted sequence faster than this anyway (without additional exploitation of some knowledge about the values).