On SkipList
published on 2022/08/07
SkipLists often come up when discussing “obscure” data-structures but in reality they are not that obscure, in fact many of the production grade softwares actively use them. In this post I’ll try to go into SkipLists by describing how to make a toy implementation, potential optimizations and real world use cases of them. So what are SkipLists anyway? Well, SkipList are referential data structures inspired from linked list and binary trees. They are collection of sort linked list arranged in different levels, where levels are designed in such a way that it allows skipping nodes to get a logarithmic complexity when searching for the keys later. They are alternative to binary trees and even in some cases the legendary B-Tree, in fact last level of SkipList looks somewhat like a B+Tree. SkipLists perform very well with random write heavy workloads where ordered storage or fast lookup is required. Construction of level(s) is probabilistic in nature, thus these lists can be vulnerable to becoming unbalanced if underlying random algorithm isn’t uniform enough. These are also typically a lot easier to implement compared to HashMaps and Trees which make them ideal for an alternative choice specially if only in memory lookup is required.