This is a simple and thread-safe skip list implemented by Go with generics.
Other than the classic Get
, Put
and Delete
, some more convenience functions are implemented that makes this skiplist implementation very easy and straight forward to use
in real applications. All complexity values are approximates, as skiplist can only approximate runtime complexity.
Function | Complexity | Description |
---|---|---|
Level | O(1) | returns the level of the skiplist |
Cap | O(1) | returns the number of invalid nodes |
Get | O(log(n)) | returns the value of a given key and whether it is valid |
Put | O(log(n)) | inserts or updates the value of a given key |
Delete | O(log(n)) | deletes a node for a given key |
Range | O(log(n)) | returns kv-pairs of a given key range |
Ceil | O(log(n)) | returns kv-pairs of the least key greater than or equal to target |
Floor | O(log(n)) | returns kv-pairs of the greatest key less than or equal to target. |
- Go version 1.18+
With Go module support, simply add the following import
import "github.com/ALong1997/skiplist"
Otherwise, run the following Go command to install the skiplist
package:
$ go get -u https://github.com/ALong1997/skiplist
package main
import (
"fmt"
"github.com/ALong1997/skiplist"
)
func main() {
sl := skiplist.NewSkipList[int, int](8, true)
for i := 1; i <= 100; i++ {
sl.Put(i, i)
}
// randomly generate level, but less than maxLevel
fmt.Println(sl.Level())
// 100
fmt.Println(sl.Cap())
// 10
if v, ok := sl.Get(10); ok {
fmt.Println(v)
}
// 10 10
// 11 11
for _, v := range sl.Range(10, 11) {
fmt.Println(v.Key(), v.Val())
}
// 1
fmt.Println(sl.Ceil(0))
// 100
fmt.Println(sl.Floor(1000))
for i := 1; i <= 100; i++ {
sl.Delete(i)
}
}