This is a library implementing skip lists for the Go programming language (http://golang.org/).
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
Skip lists were first described in Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676
$ go get github.com/ryszard/goskiplist/skiplist package main import ( "fmt" "github.com/ryszard/goskiplist/skiplist" ) func main() { s := skiplist.NewIntMap() s.Set(7, "seven") s.Set(1, "one") s.Set(0, "zero") s.Set(5, "five") s.Set(9, "nine") s.Set(10, "ten") s.Set(3, "three") firstValue, ok := s.Get(0) if ok { fmt.Println(firstValue) } // prints: // zero s.Delete(7) secondValue, ok := s.Get(7) if ok { fmt.Println(secondValue) } // prints: nothing. s.Set(9, "niner") // Iterate through all the elements, in order. unboundIterator := s.Iterator() for unboundIterator.Next() { fmt.Printf("%d: %s\n", unboundIterator.Key(), unboundIterator.Value()) } // prints: // 0: zero // 1: one // 3: three // 5: five // 9: niner // 10: ten for unboundIterator.Previous() { fmt.Printf("%d: %s\n", unboundIterator.Key(), unboundIterator.Value()) } // 9: niner // 5: five // 3: three // 1: one // 0: zero boundIterator := s.Range(3, 10) // Iterate only through elements in some range. for boundIterator.Next() { fmt.Printf("%d: %s\n", boundIterator.Key(), boundIterator.Value()) } // prints: // 3: three // 5: five // 9: niner for boundIterator.Previous() { fmt.Printf("%d: %s\n", boundIterator.Key(), boundIterator.Value()) } // prints: // 5: five // 3: three var iterator skiplist.Iterator iterator = s.Seek(3) fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 3: three iterator = s.Seek(2) fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 3: three iterator = s.SeekToFirst() fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 0: zero iterator = s.SeekToLast() fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 10: ten // SkipList can also reduce subsequent forward seeking costs by reusing the // same iterator: iterator = s.Seek(3) fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 3: three iterator.Seek(5) fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value()) // prints: // 5: five }Read it online or run
$ go doc github.com/ryszard/goskiplist/skiplist This list is probably incomplete.