#list #skip #insert

skip-list

Implementing a skip list with rust

4 releases

0.1.3 Apr 27, 2022
0.1.2 Apr 27, 2022
0.1.1 Apr 26, 2022
0.1.0 Apr 25, 2022

#9 in #skip

38 downloads per month
Used in velarixdb

MIT license

19KB
344 lines

skip-list

Implementing a skip list with rust

Examples

let mut skip_list = SkipList::default();
// insert
assert_eq!(skip_list.insert(1, 10), None); // there is no value with key with 1
assert_eq!(skip_list.insert(2, 20), None);
assert_eq!(skip_list.insert(3, 30), None);

// get
assert_eq!(skip_list.get(&1), Some(&10));
assert_eq!(skip_list.get(&2), Some(&20));
assert_eq!(skip_list.get(&3), Some(&30));

// update
assert_eq!(skip_list.insert(1, 100), Some(10)); // return old data
assert_eq!(skip_list.insert(2, 200), Some(20));
assert_eq!(skip_list.insert(3, 300), Some(30));

// iterator
for (k, v) in skip_list.iter() {
    let value = k * 100;
    assert_eq!(*v, value);
}

// delete
assert_eq!(skip_list.delete(&1), Some(100));
assert_eq!(skip_list.delete(&10), None);
assert_eq!(skip_list.get(&1), None);

lib.rs:

Implementing a skip list with Rust. The SkipList supports insert, get, delete and iterator such as iter, iter_mut, into_iter. The default max level of skip list is 12 when use SkipList::default(). The max level of skip list can be customized by SkipList::new(max_level: usize).

Example

use skip_list::SkipList;

let mut skip_list = SkipList::default();
assert_eq!(skip_list.insert(1, 10), None); // there is no value with key with 1
assert_eq!(skip_list.insert(2, 20), None);
assert_eq!(skip_list.insert(3, 30), None);

// get
assert_eq!(skip_list.get(&1), Some(&10));
assert_eq!(skip_list.get(&2), Some(&20));
assert_eq!(skip_list.get(&3), Some(&30));

// update
assert_eq!(skip_list.insert(1, 100), Some(10));
assert_eq!(skip_list.insert(2, 200), Some(20));
assert_eq!(skip_list.insert(3, 300), Some(30));

// iterator
for (k, v) in skip_list.iter() {
    let value = k * 100;
    assert_eq!(*v, value);
}

// delete
assert_eq!(skip_list.delete(&1), Some(100));
assert_eq!(skip_list.delete(&10), None);
assert_eq!(skip_list.get(&1), None);

Dependencies

~315KB