Skip to content

A fast, performant implementation of skip list in Rust.

License

Notifications You must be signed in to change notification settings

sushrut141/subway

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

28 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Subway

skiplist image

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.

Build License: MIT

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)