Home

Awesome

Skiplist

Latest Version Build Status Go Documentation Go Report Card Maintainability Test Coverage

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