Awesome
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