# Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little example?), I can only find so little about it online. Thanks.

• (Please add what contents found here you think should have helped, and how it didn't.) – greybeard Dec 6 '19 at 4:22

An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $$m$$th entry (in order) in a skiplist in $$O(\log n)$$ time in a skiplist of $$n$$ entries. In other words, it takes a skiplist that is not an indexable skiplist $$O(n)$$ time, on average, to find the $$m$$th element in order in a skiplist, while an ordered skiplist can do this in logarithmic time.