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.10: 0.12 Wed Nov 19 2003 - added validate_key and validate_node methods to Node 0.11 Sun Nov 16 2003 - modified test script to better check next_key function - bug fix: next_key did not check that $last_key existed CAVEATS This is a prototype module and may contain bugs. 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.