1
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

It does this by keeping track of the width of the links in the skiplist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.