Home

Awesome

Skip List in Golang

Go Go Doc Go Report Coverage Status

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

Highlights in this implementation:

Install

Install this package through go get.

    go get github.com/huandu/skiplist

Basic Usage

Here is a quick sample.

package main

import (
    "fmt"

    "github.com/huandu/skiplist"
)

func main() {
    // Create a skip list with int key.
    list := skiplist.New(skiplist.Int)

    // Add some values. Value can be anything.
    list.Set(12, "hello world")
    list.Set(34, 56)
    list.Set(78, 90.12)

    // Get element by index.
    elem := list.Get(34)                // Value is stored in elem.Value.
    fmt.Println(elem.Value)             // Output: 56
    next := elem.Next()                 // Get next element.
    prev := next.Prev()                 // Get previous element.
    fmt.Println(next.Value, prev.Value) // Output: 90.12    56

    // Or, directly get value just like a map
    val, ok := list.GetValue(34)
    fmt.Println(val, ok) // Output: 56  true

    // Find first elements with score greater or equal to key
    foundElem := list.Find(30)
    fmt.Println(foundElem.Key(), foundElem.Value) // Output: 34 56

    // Remove an element for key.
    list.Remove(34)
}

Using GreaterThanFunc and LessThanFunc

Define your own GreaterThanFunc or LessThanFunc to use any custom type as the key in a skip list.

The signature of GreaterThanFunc are LessThanFunc are the same. The only difference between them is that LessThanFunc reverses result returned by custom func to make the list ordered by key in a reversed order.

type T struct {
    Rad float64
}
list := New(GreaterThanFunc(func(k1, k2 interface{}) int {
    s1 := math.Sin(k1.(T).Rad)
    s2 := math.Sin(k2.(T).Rad)

    if s1 > s2 {
        return 1
    } else if s1 < s2 {
        return -1
    }

    return 0
}))
list.Set(T{math.Pi / 8}, "sin(π/8)")
list.Set(T{math.Pi / 2}, "sin(π/2)")
list.Set(T{math.Pi}, "sin(π)")

fmt.Println(list.Front().Value) // Output: sin(π)
fmt.Println(list.Back().Value)  // Output: sin(π/2)

License

This library is licensed under MIT license. See LICENSE for details.