skiplist

README

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

• skip list entry in wikipedia
• "A skip list cookbook" by William Pugh (pdf)

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.

Documentation

Overview

Package skiplist provides a skip list implementation based on W. Pugh's work

Index

• Constants
• func New(lteq func(l, r interface{}) bool) skipList
• func NextIterator(lst skipList) func() interface{}

Constants

const (
	Height int = 32
)

Functions

func New

func New(lteq func(l, r interface{}) bool) skipList

func NextIterator

func NextIterator(lst skipList) func() interface{}

Iterator returning a function that returns the next value in a list