Algorithm::SkipList 2.00_02

Algorithm::SkipList is a Perl implementation of skip lists.

SYNOPSIS

my $list = new Algorithm::SkipList();

$list->insert( 'key1', 'value' );
$list->insert( 'key2', 'another value' );

$value = $list->find('key2');

$list->delete('key1');

This is an 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, like so:

4 +---------------------------> +----------------------> +
| | |
3 +------------> +------------> +-------> +-------> +--> +
| | | | | |
2 +-------> +--> +-------> +--> +--> +--> +-------> +--> +
| | | | | | | | |
1 +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +--> +
A B C D E F G H I J NIL

A search would start at the top level: if the link to the right exceeds the target key, then it descends a level.

Skip lists generally perform as well as balanced trees for searching but do not have the overhead with respect to inserting new items. See the included file Benchmark.txt for a comparison of performance with other Perl modules.


Product's homepage

Requirements:

· Perl

What's New in This Release: [ read full changelog ]

· Rewrote Algorithm::SkipList::Node. Now based on the Tree::Node package, which is written in C for significant improvement in memory usage, and a slight improvement in speed
· Cleaner code in various methods
· Option to set minimum level