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 time required growing in O(n). The raw numbers are even more impressive:
| Size | Skip list [avg ns] | Linked list [avg ns] |
| 1,000 | 311 | 825 |
| 10,000 | 438 | 17,574 |
| 100,000 | 1,190 | 428,259 |
| 1,000,000 | 2,609 | 5,440,420 |
| 10,000,000 | 3,334 | 45,157,562 |
These numbers reflect the nanoseconds (ns) required for a single call to the find() method averaged over...
