Subway

A fast, performant implementation of skip list in Rust.
A skip list is probabilistic data structure that provides O(log N) search and insertion complexity.
For more information about how to skiplist work refer here.

Usage

The SkipList supports the following operations.

`insert`

Insert an element into the list while maintaining sorted order.
The insert method accepts a key and a value.
The values in the list will be stored sorted by key.

let list = SkipList::new();
list.insert(1, 1);
list.insert(2, 2);

`get`

Returns an optional value if the supplied key is found in the list.
Time complexity of this operation is around O(logN).

let maybe_value = list.get(&key);
if maybe_value.is_some() {
    let value = maybe_value.unwrap();
}

`delete`

Deletes an item from the linked list if present using the supplied key.

list.delete(&key_to_delete);

`collect`

Collects the list of items in the skip list sorted by key into a list.

list.insert(2, 2);
list.insert(1, 1);
list.insert(5, 5);
let values = list.collect(); // (1, 1), (2, 2), (5, 5)

Comments

Skip List insertion is slow

Description

The current insert implementation inserts into each level of the skip list. Using the bisect method it is possible to obtain insertion points across all levels in logarithmic time and insert new nodes after each of those points if required.
bug

opened by sushrut141 1
Implement bisect method for SkipList

The bisect should return the rightmost position where an element can be inserted to keep the list sorted. The bisect method should return the key present at this rightmost position.
enhancement

opened by sushrut141 0

Releases(v0.1.1)

v0.1.1(Mar 13, 2021)

The bisect method allows for efficiently finding the insertion point in the list. Specifically, bisect returns the largest key after which the the supplied key can be inserted in the list.
Source code(tar.gz)
Source code(zip)
v0.1.0(Feb 4, 2021)

This is the first release of subway to crates.io
Source code(tar.gz)
Source code(zip)