dc.contributor.author | Pugh, William | en_US |
dc.date.accessioned | 2004-05-31T22:20:55Z | |
dc.date.available | 2004-05-31T22:20:55Z | |
dc.date.created | 1990-06 | en_US |
dc.date.issued | 1998-10-15 | en_US |
dc.identifier.uri | http://hdl.handle.net/1903/544 | |
dc.description.abstract | Skip lists are a probabilistic list-based data structure that are
a simple and efficient substitute for balanced trees. Skip list algorithms
have the same asymptotic expected time bounds as balanced trees and are
simpler, faster and use less space. The original paper on skip lists only
presented algorithms for search, insertion and deletion. In this paper, we
show that skip lists are as versatile as balanced trees. We describe and
analyze algorithms to use search fingers, merge, split and concatenate
skip lists, and implement linear list operations using skip lists. The
skip list algorithms for these actions are simpler than their balanced
tree cousins and at least as fast. The merge algorithm for skip lists we
describe has better asymptotic time complexity than any previously
described merge algorithm for balanced trees.
(Also cross-referenced as UMIACS-TR-89-72.1) | en_US |
dc.format.extent | 276610 bytes | |
dc.format.mimetype | application/postscript | |
dc.language.iso | en_US | |
dc.relation.ispartofseries | UM Computer Science Department; CS-TR-2286.1 | en_US |
dc.relation.ispartofseries | UMIACS; UMIACS-TR-89-72.1 | en_US |
dc.title | A Skip List Cookbook | en_US |
dc.type | Technical Report | en_US |
dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |