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 History Skip lists were first described in 1989 by William Pugh. To quote the author: Usages List of applications and frameworks that use skip lists: Apache Portable Runtime implements skip lists. MemSQL uses lock-free skip lists as its prime indexing structure for its database technology. MuQSS built on skip lists as a cpu scheduler. Cyrus IMAP server offers a "skiplist" backend DB implementation Lucene uses skip lists to search delta-encoded posting lists in logarithmic time. The "QMap" key/value dictionary (up to Qt 4) template class of Qt is implemented with skip lists. Redis, an ANSI-C open-source persistent key/value store for Posix systems, uses skip lists in its implementation of ordered sets. "nessDB", a very fast key-value embedded Database Storage Engine (Using log-structured-merge (LSM) trees), uses skip lists for its