Hop lists(dekorte.com)

4 pointsby epe18 lat temu1 comments

http://www.dekorte.com/blog/blog.cgi?do=item&id=3804

1 comments

ganley18 lat temu

At a glance, I'm pretty sure this doesn't work. The average jump is not to the bisection between the current node and the node you're seeking, it's to the bisection between the current node and the end of the list. As you get closer to the node you seek, the probability gets higher and higher that the skip link points past the node you seek, in which case it does nothing for you and you continue sequentially searching. I haven't done the math, but I think the expected search is O(n) - though possibly faster in practice than a simple sequential search.