SkipList in Go
Algorithmic thinking is the must-have in the coding world, so I have been keeping the routine of algorithm practice every week, consolidating my knowledge of data structures on one hand, and improving my coding skills as well.
A difficult one happened to be stuck in my mind- Implement SkipList with Go, which took me quite a weekend. Below is the front-line report of how I finally got the hang of it.
First, from its concept. Wiki has explained it well.
a skip list is a probabilistic data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements.
In short, SkipList is a multi-layer-structured sort list for efficient queries. The bottom layer is an ordered LinkedList, and the upper layer extracts the bottom list and decomposes it into multiple lists that only contain certain index nodes.
To speed up queries, SkipList is adopted in many open-source libraries related to database storage. As far as I know, there are
