The Complete Rust Programming Reference Guide

Thoughts and discussion

skip list is a fascinating data structure, as it is fairly simple to implement and combines the benefits of tree-like structures within a list without the need for expensive inserts or rebalancing. To visualize the power of this data structure, here is a chart that compares the find() operation of skip lists and (std::collections::) LinkedList:

The graph output for Skip List find () and Linked List find ()

The first chart (higher) shows how the skip list behaves according to an O(log n) type function, which proves that the implementation works! The second (lower) chart shows the linear search in LinkedList, with the ...