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.