Skiplist

Skiplist implementation in Go. Read more on Skip Lists

Skiplist with various additions and potential variations on the standard list.

Install

go get -u github.com/mtchavez/skiplist

Usage

Initialize a skiplist

package main

func main() {
    list := skiplist.NewList()
}

Insert Nodes

package main

func main() {
    list := skiplist.NewList()
    list.Insert(1, []byte("Node 1"))
    list.Insert(2, []byte("Node 2"))
}

Iterate through nodes

package main

import (
    "fmt"
)

func main() {
    list := skiplist.NewList()
    list.Insert(1, []byte("Node 1"))
    list.Insert(2, []byte("Node 2"))
    list.Insert(3, []byte("Node 3"))

    for i := list.Iterator(); i.Next(); {
        // Print Key
        fmt.Println(i.Key())

        // Print Value
        fmt.Println(i.Val())
    }
}

Documentation

Docs are on GoDoc

Tests

Run tests with coverage

go test --cover

Benchmarks

Benchmarked with on a 2.3 GHz Intel Core i7.

# Benchmarked on 2017-09-16
goos: darwin
goarch: amd64
pkg: github.com/mtchavez/skiplist
BenchmarkInsert_1000-8              2000            805488 ns/op
BenchmarkInsert_10000-8              200           8370616 ns/op
BenchmarkInsert_100000-8              20          98251825 ns/op
BenchmarkInsert_1000000-8              1        1122310227 ns/op
BenchmarkParallelInsert-8        1000000              1349 ns/op
BenchmarkDelete_1000-8              5000            221056 ns/op
BenchmarkDelete_10000-8              500           3577634 ns/op
BenchmarkDelete_100000-8              30          61547826 ns/op
BenchmarkDelete_1000000-8              2         611290978 ns/op
BenchmarkParallelDelete-8        2000000               802 ns/op

TODO

• Implement a compare interface
• Concurrent skiplist implementation