Search code examples
javadata-structuresskip-lists

Does java have a skip list implementation

I find ConcurrentSkipListSet in Java Collection Framework, which is backed up with a skip list. But is there a skip list in Java? A set does not work in my use case. I need a indexable list that supports duplicates.

Solution

  • Since you've mentioned a List that is both Indexable (I assume you want speedy retrieval) and need to allow duplicates, I would advise you go for a custom Set with a LinkedList or ArrayList perhaps.

    You need to have a base Set, an HashSet for example and keep adding values to it. If you face a duplicate, the value of that Set should point to a List. So, that you will have both Speedy retrieval and of course you will store your objects in a psuedo Collection manner.

    This should give you good efficiency for retrieval. Ideally if your Keys are not duplicates, you will achieve an O(1) as the retrieval speed.