Skiplist is a go (golang) package implementing a skip list. The skip list was invented by William Pugh, see references below for performance and more details.
My implementation is using a ‘head’ pointer to point to the first node which is a empty (key & value are nil) node – a sentinel – created and inserted in the construction of the list.
I am also calculating the probability of the height of a new node to be inserted instead of simulating a coin toss.
The probability p of an integer N,
p = 1/(2^N)
The height/levels, N, of a new node where N = [1, 2, 3, … ] and f is a random floating point number,
N = ceil(log(f)/log(0.5)), f ∈ [0,1)
So far I have only coded it up and been running the unit tests found in the test file. There might still be corner cases not yet tested, so be warned.
Note, part of the tests are random insertion/lookups, this might fail if two or more values generated are the same since the skip list are overwriting keys with the same value but they all exists in the array used for comparison.
Released under MIT license. See LICENSE file.