NAME List::SkipList - Perl implementation of skip lists REQUIREMENTS "Carp::Assert" is used for validation and debugging. (The assertions can be commented out if the module cannot be installed.) Otherwise standard modules are used. SYNOPSIS my $list = new List::SkipList(); $list->insert( 'key1', 'value' ); $list->insert( 'key2', 'another value' ); $value = $list->find('key2'); $list->delete('key1'); DESCRIPTION This is a prototype implementation of *skip lists* in Perl. Skip lists are similar to linked lists, except that they have random links at various *levels* that allow searches to skip over sections of the list. Skip lists generally perform as well as balanced trees for searching but do not have the overhead with respect to inserting new items. More information is available in the module documentation. REVISION HISTORY Changes since v0.13: 0.20 Wed Nov 26 2003 - if no last_key specified for next_key, it returns first_key - search fingers added - find, first_key, next_key return a list in list context as part of support for search fingers - minor changes to documentation CAVEATS This is a prototype module and may contain bugs. Skip lists are non-deterministic. Because of this, bugs in programs that use this module may be subtle and difficult to reproduce without many repeated attempts. AUTHOR Robert Rothenberg LICENSE Copyright (c) 2003 Robert Rothenberg. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself. SEE ALSO See the article *A Skip List Cookbook* (William Pugh, 1989), or similar ones by the author at http://www.cs.umd.edu/~pugh/ which discuss skip lists.