Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Skip list
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== Indexable skiplist === As described above, a skip list is capable of fast <math>O(\log n)</math> insertion and removal of values from a sorted sequence, but it has only slow <math>O(n)</math> lookups of values at a given position in the sequence (i.e. return the 500th value); however, with a minor modification the speed of [[random access]] indexed lookups can be improved to <math>O(\log n)</math>. For every link, also store the width of the link. The width is defined as the number of bottom layer links being traversed by each of the higher layer "express lane" links. For example, here are the widths of the links in the example at the top of the page: 1 10 o---> o---------------------------------------------------------> o Top level 1 3 2 5 o---> o---------------> o---------> o---------------------------> o Level 3 1 2 1 2 3 2 o---> o---------> o---> o---------> o---------------> o---------> o Level 2 1 1 1 1 1 1 1 1 1 1 1 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o Bottom level Head 1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th NIL Node Node Node Node Node Node Node Node Node Node Notice that the width of a higher level link is the sum of the component links below it (i.e. the width 10 link spans the links of widths 3, 2 and 5 immediately below it). Consequently, the sum of all widths is the same on every level (10 + 1 = 1 + 3 + 2 + 5 = 1 + 2 + 1 + 2 + 3 + 2). To index the skip list and find the i'th value, traverse the skip list while counting down the widths of each traversed link. Descend a level whenever the upcoming width would be too large. For example, to find the node in the fifth position (Node 5), traverse a link of width 1 at the top level. Now four more steps are needed but the next width on this level is ten which is too large, so drop one level. Traverse one link of width 3. Since another step of width 2 would be too far, drop down to the bottom level. Now traverse the final link of width 1 to reach the target running total of 5 (1+3+1). '''function''' lookupByPositionIndex(i) node β head i β i + 1 ''# don't count the head as a step'' '''for''' level '''from''' top '''to''' bottom '''do''' '''while''' i β₯ node.width[level] '''do''' ''# if next step is not too far'' i β i - node.width[level] ''# subtract the current width'' node β node.next[level] ''# traverse forward at the current level'' '''repeat''' '''repeat''' '''return''' node.value '''end function''' This method of implementing indexing is detailed in ''"A skip list cookbook"'' by William Pugh<ref> William Pugh. ''"A skip list cookbook"''. 1990. [https://drum.lib.umd.edu/items/56c44671-3973-46b6-9e52-f71dc95af178 Section 3.4 Linear List Operations ]. </ref>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)