Hands-On Data Structures and Algorithms with Rust

Jumping around

The skip list only resembles a binary search tree, but it is able to achieve the same runtime complexity (O(log n)) without the need for expensive rebalancing. This is due to the jumps the skip list allows. Logically, it makes sense: by jumping over several nodes, these nodes don't need to be looked at to find out whether those are the values that are being searched for. Fewer nodes means fewer comparisons, leading to a reduced runtime.

The jumps are quickly implemented too and can be implemented in a function using a few loops:

pub fn find(&self, offset: u64) -> Option<String> {    match self.head {        Some(ref head) => {            let mut start_level = self.max_level;            let node = head.clone();            let mut result = None;            loop {                if node.borrow ...