3 releases
0.1.2 | Mar 13, 2021 |
---|---|
0.1.1 | Mar 13, 2021 |
0.1.0 | Feb 4, 2021 |
#1930 in Algorithms
Used in dharmadb
36KB
725 lines
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)
Dependencies
~385KB