NIST

skip list

(data structure)

Definition: A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).

Generalization (I am a kind of ...)
ordered linked list.

Aggregate child (... is a part of or used in me.)
randomized algorithm.

See also jump list.

Note: A skip list may be seen as approximating binary search in a linked list.

Author: PEB

Implementation

Julienne Walker's tutorial (C). Click "Libraries", then "Classic Skip List" for the zip'd code. Code (C) at ePaperPress.

More information

(click on Dictionaries, then Skip Lists) diagrams and explanation (and code) at ePaperPress.

William Pugh, Concurrent Maintenance of Skip Lists, Tech. Report CS-TR-2222, Dept. of Computer Science, U. Maryland, April 1989.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 20 May 2014.
HTML page formatted Tue May 20 11:02:31 2014.

Cite this as:
Paul E. Black, "skip list", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 May 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/skiplist.html