A skip list implementation in Go



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

Build Status


$ go get github.com/ryszard/goskiplist/skiplist


package main

import (

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 {
	// prints:
	//  zero


	secondValue, ok := s.Get(7)
	if ok {
	// 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

	fmt.Printf("%d: %s\n", iterator.Key(), iterator.Value())
	// prints:
	//  5: five

Full documentation

Read it online or run

$ go doc github.com/ryszard/goskiplist/skiplist

Other implementations

This list is probably incomplete.

  • Improving Delete behaviour?

    Improving Delete behaviour?

    I ran into an interesting case. If a key is a pointer, as long as lessThan is defined properly, getting and setting key/value works fine.

    However, due to this line: https://github.com/ryszard/goskiplist/blob/master/skiplist/skiplist.go#L471 the comparison of the key (!=) doesn't happen correctly and goskiplist believes this is not the same key. I have worked around this by using structure directly (as opposed to a pointer to it) but I was thinking may be there's a way to fix this case?

    May be there could be an equality func defined for a custom map?

    opened by yrashk 3
  • Support amortized traversal in forward seeking.

    Support amortized traversal in forward seeking.

    Iterator has been updated to include Iterator.Seek, which follows the same protocol of SkipList.Seek. This new Seek call allows users of goskiplist to amortize traversal costs in batched forward scan operations. If the requested key occurs before the current seek point's key, SkipList resumes the search from the head of the list.

    An overview of the performance characteristics are provided:

    mtp:skiplist mtp$ go test -test.bench="." ./... PASS BenchmarkLookup16 5000000 243 ns/op BenchmarkLookup256 5000000 556 ns/op BenchmarkLookup65536 1000000 2239 ns/op BenchmarkSet16 1000000 5305 ns/op BenchmarkSet256 1000000 6356 ns/op BenchmarkSet65536 1000000 5073 ns/op BenchmarkRandomSeek 1000000 5105 ns/op BenchmarkForwardSeek 1000000 2975 ns/op BenchmarkForwardSeekReusedIterator 1000000 1881 ns/op ok github.com/ryszard/goskiplist/skiplist 96.178s

    Compare BenchmarkForwardSeek versus BenchmarkForwardSeekReusedIterator.

    I have a use case where this type of seeking performance will be tremendously beneficial in reducing operation latency.

    opened by matttproud 3
  • Question


    Why didn't you wrap it in a standard way? For example, take func Insert(&& insert) in stead of func Set. And when you random a level, whether if you would consider the thread-safe?Or, will you improve that part?? Any better way to random a level? At last, thank you too much because I've learned much from your code. Thanks again!

    opened by PaladinTyrion 2
  • Double-Linked Skip List and Arbitrary Seeking Support

    Double-Linked Skip List and Arbitrary Seeking Support

    Hey Ric,

    Attached is an implementation of the Skip List being double-linked for reverse traversal. Secondarily there is support for arbitrary seeking. If you want me to refactor this into a separate type so that the base implementation remains the same (except for keeping the arbitrary seeking support in both), I can do that. Please let me know how the base implementation looks, and I'll start the refactoring afterwards.

    This is per https://github.com/ryszard/goskiplist/issues/1.



    opened by matttproud 2
  • Doubly Linked Implementation

    Doubly Linked Implementation

    Hey @ryszard, if I were interested in providing a doubly linked implementation of this for reverse iterations, what would be your preference:

    1. Adapt your implementation type verbatim to be doubly linked?
    2. Rename your type to convey singly linked quality and create a doubly linked derivative in an idiomatic way?


    1. Not to maintain or keep a one-off of this project to reduce diffusion of effort or public attention—i.e., have the implementation be sucked into this one one by pull request.

    Let me know what your preference would be given this.

    opened by matttproud 2
  • Include SeekToFirst and SeekToLast.

    Include SeekToFirst and SeekToLast.

    Following the LevelDB iterator protocol (http://leveldb.googlecode.com/svn/trunk/doc/index.html), I have added SkipList.SeekToFirst and SkipList.SeekToLast support.

    The tests and documentation have been updated to reflect this.

    opened by matttproud 1
  • take equals instead of ==

    take equals instead of ==

    hi Ric,

    I tries take advantage of goskiplist as a sorted set in my part time project, but got this error:

    panic: runtime error: comparing uncomparable type FileMeta
    goroutine 36 [running]:
    	/usr/local/Cellar/go/1.12/libexec/src/testing/testing.go:830 +0x388
    panic(0x12e38a0, 0xc0000a0da0)
    	/usr/local/Cellar/go/1.12/libexec/src/runtime/panic.go:522 +0x1b5
    github.com/Fleurer/miaomiao/util/goskiplist/skiplist.(*SkipList).Set(0xc0000a2c90, 0x1310a00, 0xc0000b2f40, 0x0, 0x0)
    	/Users/fleuria/night/miaomiao/util/goskiplist/skiplist/skiplist.go:416 +0x62a
    github.com/Fleurer/miaomiao/tool.(*Builder).Apply(0xc00019a000, 0xc00004bed8)
    	/Users/fleuria/night/miaomiao/tool/builder.go:67 +0x31d

    FileMeta is a struct so it can not be compared using ==/!=. I've noticed there's a comment about this: Additionally, Ordered instances should behave properly when compared using == and !=. But maybe it's possible to use the lessThan function to get the equality between the values?


    opened by flaneur2020 0
  • Sometimes cannot find the key

    Sometimes cannot find the key

    in a FOR loop I push elements into the skiplist, and if the key already existed, I delete it first. but the result of Delete() is (, false).

    It happens sometimes.

    opened by cranewill 0
  • can't  use the same key ?

    can't use the same key ?

    sorry , can u let goskiplist to support set the same key feature.


    s := skiplist.NewIntMap()
    s.Set(7, "seven")
    s.Set(7, "kkk")
    output: kkk

    but, i want to get all values . seven and kkk . how to use ? thank u .

    opened by rfyiamcool 0
Ric (Ryszard) Szopa
Ric (Ryszard) Szopa
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Huan Du 304 Dec 4, 2022
skipmap is a high-performance concurrent sorted map based on skip list. Up to 3x ~ 10x faster than sync.Map in the typical pattern.

Introduction skipmap is a high-performance concurrent map based on skip list. In typical pattern(one million operations, 90%LOAD 9%STORE 1%DELETE), th

ZhangYunHao 106 Jan 8, 2023
A skip list of arbitrary elements that can be filtered using roaring bitmaps stored in an LRU cache

Skipfilter This package provides a data structure that combines a skiplist with a roaring bitmap cache. This library was created to efficiently filter

Kevin Burns 22 Aug 4, 2022
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

sean 240 Dec 2, 2022
Most comprehensive list :clipboard: of tech interview questions :blue_book: of companies scraped from Geeksforgeeks, CareerCup and Glassdoor.

Companies* Companies E Expedia G Grab M MobiKwik N NEC Technologies P PayPal S Samsung Research Institute U Uber Y Yatra.com Z Zomato Announcements ??

Twowaits 6.4k Dec 29, 2022
The first generic linked list in go :dancer:

linkedlist.go The first generic linked list in go ?? gotip first of all you need to install the master version of golang. go install golang.org/dl/got

Parham Alvani 26 Dec 7, 2022
Advanced linked list package for go.

golib/list ライブラリ 可変長の連結リストを提供するライブラリーです。 状況によらず、メモリ開放処理を一貫性した書き方で実装できるので、メモリ解放をプログラマが管理しやすい作りになっています。 list.List 片方向連結リストを提供するモジュールです。 list.Nodeが使われていま

null 0 Jan 21, 2022
Go implementation of Count-Min-Log

Count-Min-Log Count-Min-Log sketch: Approximately counting with approximate counters - Guillaume Pitel & Geoffroy Fouquier TL;DR: Count-Min-Log Sketch

Seif Lotfy 59 Jan 4, 2023
A Go implementation of the Elias-Fano encoding

go-ef A Go implementation of the Elias-Fano encoding Example package main import ( "fmt" "github.com/amallia/go-ef" "os" ) func main() {

Antonio Mallia 27 Nov 23, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022
Go implementation of C++ STL iterators and algorithms.

iter Go implementation of C++ STL iterators and algorithms. Less hand-written loops, more expressive code. README translations: 简体中文 Motivation Althou

disksing 170 Dec 19, 2022
Go implementation to calculate Levenshtein Distance.

levenshtein Go package to calculate the Levenshtein Distance The library is fully capable of working with non-ascii strings. But the strings are not n

Agniva De Sarker 253 Dec 14, 2022
A Merkle Tree implementation written in Go.

Merkle Tree in Golang An implementation of a Merkle Tree written in Go. A Merkle Tree is a hash tree that provides an efficient way to verify the cont

Cameron Bergoon 406 Jan 5, 2023
A prefix tree implementation in go

Trie (Prefix tree) This library is compatible with Go 1.11+ Please refer to CHANGELOG.md if you encounter breaking changes. Motivation Introduction Us

Viant, Inc 31 Nov 3, 2022
Package ring provides a high performance and thread safe Go implementation of a bloom filter.

ring - high performance bloom filter Package ring provides a high performance and thread safe Go implementation of a bloom filter. Usage Please see th

Tanner Ryan 130 Nov 20, 2022
A simple Set data structure implementation in Go (Golang) using LinkedHashMap.

Set Set is a simple Set data structure implementation in Go (Golang) using LinkedHashMap. This library allow you to get a set of int64 or string witho

Studio Sol Comunicação Digital Ltda 22 Sep 26, 2022
A slice-based implementation of a stack. In Go!

Stackgo Stackgo is a slice-based implementation of a simple stack in Go. It uses a pre-alloc pagination strategy which adds little memory overhead to

Alessandro Diaferia 16 Nov 3, 2022
A Left-Leaning Red-Black (LLRB) implementation of balanced binary search trees for Google Go

GoLLRB GoLLRB is a Left-Leaning Red-Black (LLRB) implementation of 2-3 balanced binary search trees in Go Language. Overview As of this writing and to

Petar Maymounkov 747 Dec 23, 2022
Golang implementation of Radix trees

go-radix Provides the radix package that implements a radix tree. The package only provides a single Tree implementation, optimized for sparse nodes.

Armon Dadgar 768 Dec 30, 2022