Rust-Skiplist

A skiplist is a way of storing ordered elements with $mathcal{O}(log n)$ retrieval complexity and $mathcal{O}(log n)$ insertion complexity. This package is an implementation of skiplists inside Rust

Conceptually, the skiplist contains a number of levels, with the bottom-most level being a regular linked list. Each level above done contains a subset of the elements of the level below it with some probability $p in (0, 1)$ . This is illustrated below:

text

	<head> ----------> [2] --------------------------------------------------> [9] ---------->
	<head> ----------> [2] ------------------------------------[7] ----------> [9] ---------->
	<head> ----------> [2] ----------> [4] ------------------> [7] ----------> [9] --> [10] ->
	<head> --> [1] --> [2] --> [3] --> [4] --> [5] --> [6] --> [7] --> [8] --> [9] --> [10] ->

The traversal of the skiplist starts at the top-most <head> node and moves right and down until it finds the desired element. By starting with the top-most layer, the algorithm can skip over large portions of the list thereby reducing the complexity of the algorithm. For example, if finding the element 8 in the above skiplist, the algorithm would visit <head> -> [2] -> [4] -> [7] -> [8].

In order to use this crate, simply add it to your dependencies:

	cargo add skiplist

Usage

The skiplist can be used as follows:

rust

	use skiplist::SkipList;
	
	fn main() {
	  let mut list = SkipList::new();
	
	  for i in 0..10 {
	    list.insert(i);
	  }
	
	  assert_eq!(list.len(), 10);
	}

The library also offers two alternative collections, SkipSet and SkipMap. The SkipSet functions as an ordered set of elements where repeated elements are ignored. The SkipMap functions as an ordered map of keys to values where repeated keys are ignored.

rust

	use skiplist::{SkipSet, SkipMap};
	
	fn main() {
	  let mut set = SkipSet::new();
	
	  for i in 0..10 {
	    set.insert(i % 3);
	  }
	
	  // The only elements within the set will be 0, 1, and 2
	  assert_eq!(set.len(), 3);
	
	  let mut map = SkipMap::new();
	
	  for i in 0..10 {
	    map.insert(i, i % 3);
	  }
	
	  assert_eq!(map.len(), 10);
	  assert_eq!(map.get(&3), Some(&0));
	}