# 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:

```
<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:

```
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.

```
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));
}
```