The Central Go Modules Repository

To use GoCenter:
export GOPROXY=https://gocenter.io
0
Stars
MIT
License
4
Downloads
January 1st 0001
Last Modified
Version:
Loading...

Skiplist

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.

References

Implementation

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)

Status

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.

License

Released under MIT license. See LICENSE file.