3 ms·
> * i find the structure of the skiplists intricate and fascinating as a thought experiment, but i feel they difficult for certain things, like implementing an
by pygy_ 16y ago
> * i find the structure of the skiplists intricate and fascinating as a thought experiment, but i feel they difficult for certain things, like implementing an iterator over them.*
Skip lists are augmented single-linked lists. You can traverse likewise.
See the python implementation[1] and its lua port[2].
1. http://code.activestate.com/recipes/576930/ http://code.activestate.com/recipes/576930/
2. http://love2d.org/wiki/Skip_list http://love2d.org/wiki/Skip_list
- kamechan 16y agohmm, yeah those iterators are nice and simple. it's been a few years since i've worked with skiplists and i remember some kind of complexity/hangup with them, but darned if i can find what that could have been looking at those clean python implementations. TODO: go back and take a look at skiplists again. PS: skiplists in haskell http://j.mp/ge5Voi http://j.mp/ge5Voi