Show simple item record

A Skip List Cookbook

dc.contributor.authorPugh, Williamen_US
dc.description.abstractSkip 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.extent276610 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-2286.1en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-89-72.1en_US
dc.titleA Skip List Cookbooken_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record