Mastering Skip Lists in Go: A Simple Probabilistic Alternative to Balanced Trees

Skip lists are a probabilistic data structure that can replace balanced trees; Redis's sorted set (zset) and LevelDB use them. This article introduces the basic principle and provides a simple Go implementation.

Skip lists use multiple forward pointers per node, achieving O(log n) average complexity while being simpler and more space‑efficient than balanced trees.

Advantages of skip lists include easier insertion and deletion, simpler implementation, lower memory usage, and better extensibility.

Insertion and deletion are simpler than in balanced trees

Implementation is straightforward

More space‑efficient

Easier to extend

Interface Design

The skip list supports float64 keys and values of any type, with operations Search, Insert, Delete, Len, Front, and Next.

package skiplist_test

import (
    "fmt"
    "github.com/protream/go-datastructures/skiplist"
)

func ExampleSkipList() {
    sl := skiplist.New()

    sl.Insert(float64(100), "foo")

    e, ok := sl.Search(float64(100))
    fmt.Println(ok)
    fmt.Println(e.Value)
    e, ok = sl.Search(float64(200))
    fmt.Println(ok)
    fmt.Println(e)

    sl.Insert(float64(20.5), "bar")
    sl.Insert(float64(50), "spam")
    sl.Insert(float64(20), 42)

    fmt.Println(sl.Len())
    e = sl.Delete(float64(50))
    fmt.Println(e.Value)
    fmt.Println(sl.Len())

    for e := sl.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
    // Output:
    // true
    // foo
    // false
    // <nil>
    // 4
    // spam
    // 3
    // 42
    // bar
    // foo
}

Definitions

Constants maxLevel and probability p control the maximum height and level distribution.

const (
    maxLevel int   = 16 // Should be enough for 2^16 elements
    p        float32 = 0.25
)

Node definition:

// Element is an element of a skiplist.
type Element struct {
    Score   float64
    Value   interface{}
    forward []*Element
}

func newElement(score float64, value interface{}, level int) *Element {
    return &Element{
        Score:   score,
        Value:   value,
        forward: make([]*Element, level),
    }
}

SkipList struct and constructor:

// SkipList represents a skiplist.
// The zero value of SkipList is an empty skiplist ready to use.
type SkipList struct {
    header *Element // header is a dummy element
    len    int      // current skiplist length, header not included
    level  int      // current skiplist level, header not included
}

// New returns a new empty SkipList.
func New() *SkipList {
    return &SkipList{
        header: &Element{forward: make([]*Element, maxLevel)},
    }
}

Random Level

func randomLevel() int {
    level := 1
    for rand.Float32() < p && level < maxLevel {
        level++
    }
    return level
}

Iteration

Front and Next methods enable sequential traversal of the skip list.

// Front returns first element in the skiplist which may be nil.
func (sl *SkipList) Front() *Element {
    return sl.header.forward[0]
}

// Next returns first element after e.
func (e *Element) Next() *Element {
    if e != nil {
        return e.forward[0]
    }
    return nil
}

Search

Search proceeds from the highest level down, locating the predecessor at each level.

// Search the skiplist to find element with the given score.
// Returns (*Element, true) if the given score is present, otherwise returns (nil, false).
func (sl *SkipList) Search(score float64) (element *Element, ok bool) {
    x := sl.header
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Score < score {
            x = x.forward[i]
        }
    }
    x = x.forward[0]
    if x != nil && x.Score == score {
        return x, true
    }
    return nil, false
}

Insert

Insertion locates update points for each level, creates a new element, and adjusts pointers.

// Insert (score, value) pair to the skiplist and returns pointer of element.
func (sl *SkipList) Insert(score float64, value interface{}) *Element {
    update := make([]*Element, maxLevel)
    x := sl.header
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Score < score {
            x = x.forward[i]
        }
        update[i] = x
    }
    x = x.forward[0]

    // Score already present, replace value.
    if x != nil && x.Score == score {
        x.Value = value
        return x
    }

    level := randomLevel()
    if level > sl.level {
        level = sl.level + 1
        update[sl.level] = sl.header
        sl.level = level
    }
    e := newElement(score, value, level)
    for i := 0; i < level; i++ {
        e.forward[i] = update[i].forward[i]
        update[i].forward[i] = e
    }
    sl.len++
    return e
}

Delete

Deletion is similar to insertion, updating pointers and decreasing the length.

// Delete remove and return element with given score, return nil if element not present
func (sl *SkipList) Delete(score float64) *Element {
    update := make([]*Element, maxLevel)
    x := sl.header
    for i := sl.level - 1; i >= 0; i-- {
        for x.forward[i] != nil && x.forward[i].Score < score {
            x = x.forward[i]
        }
        update[i] = x
    }
    x = x.forward[0]

    if x != nil && x.Score == score {
        for i := 0; i < sl.level; i++ {
            if update[i].forward[i] != x {
                return nil
            }
            update[i].forward[i] = x.forward[i]
        }
        sl.len--
    }
    return x
}

Conclusion

This article presents a straightforward Go implementation of a skip list, noting that concurrency safety can be added with sync.RWLock. For a deeper dive, refer to the original paper "Skip Lists: A Probabilistic Alternative to Balanced Trees".