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 implementation:
- Built-in types can be used as key with predefined key types. See Int and related constants as a sample.
- Support custom comparable function so that any type can be used as key.
- Key sort order can be changed quite easily. See Reverse and LessThanFunc.
- Rand source and max level can be changed per list. It can be useful in performance critical scenarios.
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
// 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.
0 Jan 26, 2022
412 Dec 26, 2022
86 Nov 11, 2022
128 Dec 24, 2022
478 Jan 3, 2023
125 Nov 3, 2022
52 Oct 7, 2022
266 Dec 19, 2022
236 Sep 21, 2022
240 Dec 30, 2022
106 Jan 8, 2023
22 Aug 4, 2022
6.4k Dec 29, 2022
26 Dec 7, 2022
0 Jan 21, 2022
344 Dec 3, 2022
623 Dec 27, 2022
248 Dec 25, 2022