<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">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-&gt;insert( 'key1', 'value' );
      $list-&gt;insert( 'key2', 'another value' );

      $value = $list-&gt;find('key2');

      $list-&gt;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.21  Wed Nov 26 2003
	- bug fix: first_key method returns a proper finger
	- added documentation and tests about memoization

    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 &lt;rrwo@cpan.org&gt;

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.
</pre></body></html>