Concurrent Skip List — Junior Level¶

Table of Contents¶

1. Introduction
2. Prerequisites
3. Glossary
4. Core Concepts
5. Real-World Analogies
6. Mental Models
7. Pros and Cons
8. Use Cases
9. Code Examples
10. Coding Patterns
11. Clean Code
12. Product Use and Feature
13. Error Handling
14. Security Considerations
15. Performance Tips
16. Best Practices
17. Edge Cases and Pitfalls
18. Common Mistakes
19. Common Misconceptions
20. Tricky Points
21. Test
22. Tricky Questions
23. Cheat Sheet
24. Self-Assessment Checklist
25. Summary
26. What You Can Build
27. Further Reading
28. Related Topics
29. Diagrams and Visual Aids

Introduction¶

Focus: "What is a skip list? Why is it 'concurrent'? When would I reach for one in Go?"

A skip list is a sorted, in-memory data structure that behaves like a balanced binary search tree but is implemented as a stack of linked lists. The bottom list contains every key, in sorted order. The list above it contains some of those keys (each one promoted with probability p, usually 1/2). The list above that contains some of those, and so on, up to a maximum height. Searching starts from the highest level of the head sentinel, races forwards while the next key is less than the target, drops down when it has to, and finishes at level 0. The expected number of steps is O(log n).

A concurrent skip list keeps the same shape, but multiple goroutines may search, insert, and delete simultaneously. The naive way is to wrap a sequential skip list in a single mutex — correct, but it serialises every operation. A better way uses fine-grained locks: one mutex per node. The best way uses lock-free updates with CAS (Compare-And-Swap) on each next pointer and marker nodes to make deletion linearisable. This file is about understanding the structure itself, the why of the layers, and writing a simple, correct, single-threaded version first. The hard part — making it correct under concurrent updates — is unpacked in the middle, senior, and professional files.

Two facts make skip lists worth learning:

1. They are simpler to make concurrent than balanced trees. There is no rotation. An insert touches one new node at every level it appears in. A delete unlinks one node from every level it appears in. The graph is local, vertical, and shallow.
2. They are ordered. Unlike sync.Map, which is a hash map and gives you O(1) average lookup but no order, a skip list gives you O(log n) lookup plus cheap forward range scans, Min, Max, and Range(lo, hi). That is why memtables in LSM-tree databases (LevelDB, RocksDB, BadgerDB) are built on skip lists.

After reading this file you will:

• Know what a skip list is and be able to draw one on paper from a list of keys.
• Understand why each new key picks its height randomly, and why that gives O(log n) expected cost.
• Be able to implement a single-threaded Insert, Contains, and Delete.
• Understand the difference between coarse-grained (single mutex), fine-grained (per-node mutex), and lock-free (CAS + markers) concurrency strategies, even before seeing the code.
• Know when to reach for a skip list versus sync.Map, a map behind a mutex, or a sorted slice.
• Have heard of, but not yet implemented, the key concurrent skip list algorithms (Pugh, Fraser, Harris–Michael) and the most popular Go library, github.com/zhangyunhao116/skipset.

You do not yet need to understand lock-free CAS sequences, marker nodes, hazard pointers, or epoch-based reclamation. Those belong to senior and professional levels.

Prerequisites¶

• Required: A Go installation, version 1.21 or newer. Check with go version.
• Required: Familiarity with structs, pointers, and methods on pointer receivers.
• Required: Comfort with linked lists. You should be able to write a singly-linked list with Insert and Delete from memory.
• Required: Familiarity with goroutines, sync.Mutex, and sync.RWMutex at the level of "I can write a concurrent counter."
• Helpful: Awareness that map in Go is not safe for concurrent writes.
• Helpful: A sense of O(log n) versus O(n) — why doubling input doubles vs adds a constant to the work.

If you can write a type LinkedList struct{ head *node } with Insert(v int) and run a test in 30 minutes without reaching for the internet, you are ready.

Glossary¶

Core Concepts¶

The journey of one key — a walkthrough¶

Before we look at code, walk through the lifecycle of one key, 42, in a skip list initially containing 10, 20, 30, 40, 50, 60, 70. With p = 1/2 you might end up with this layout:

L2:  H -----------------> 30 -----------> 60 -> nil
L1:  H -----> 20 -------> 30 -> 40 -----> 60 -----> nil
L0:  H -> 10  20 -------> 30 -> 40 -> 50 -> 60 -> 70 -> nil

Step 1 — search for the insertion point. Start at the head, at level 2. H.next[2] = 30. 30 < 42, advance. 30.next[2] = 60. 60 ≥ 42, drop down. Now at node 30, level 1. 30.next[1] = 40. 40 < 42, advance. 40.next[1] = 60. 60 ≥ 42, drop down. Now at node 40, level 0. 40.next[0] = 50. 50 ≥ 42, stop. The insertion point is "after 40 on level 0," and our recorded predecessors are update[2] = H, update[1] = 30, update[0] = 40.

Step 2 — pick a random height. Coin flip: heads, promote to level 1. Coin flip: tails, stop. h = 2.

Step 3 — splice in the new node. At level 0: new.next[0] = update[0].next[0] = 50; update[0].next[0] = new. At level 1: new.next[1] = update[1].next[1] = 60; update[1].next[1] = new.

The structure becomes:

L2:  H -----------------> 30 -------------------> 60 -> nil
L1:  H -----> 20 -------> 30 -> 40 -> 42 -------> 60 -> nil
L0:  H -> 10  20 -------> 30 -> 40 -> 42 -> 50 -> 60 -> 70 -> nil

That walkthrough — search, record, splice — is the entire algorithm. Delete is the mirror image: search, record, unlink.

A skip list is a "stack of sorted linked lists"¶

Imagine the sorted sequence 1 3 4 7 9 12 14 19 22 25 31. At level 0 you have all eleven keys linked left-to-right:

L0: H -> 1 -> 3 -> 4 -> 7 -> 9 -> 12 -> 14 -> 19 -> 22 -> 25 -> 31 -> nil

To search this list for 22 you walk linearly: 11 hops in the worst case. That is O(n). Skip lists fix that by adding express lanes on top of the base lane. Suppose each key, by a coin flip, is promoted to level 1 with probability 1/2. You might get:

L1: H -------> 3 ------> 7 ----------> 14 -------> 22 -------> 31 -> nil
L0: H -> 1 -> 3 -> 4 -> 7 -> 9 -> 12 -> 14 -> 19 -> 22 -> 25 -> 31 -> nil

To search for 22 you now ride the express lane L1 until you reach a node whose key is ≥ 22. You stop at 22 itself. If you had searched for 19, you would walk L1 to 22, realise 22 > 19, drop down to L0 at the previous node (14), and continue on L0 until you hit 19. The expected number of hops drops to O(log n).

You can repeat the trick:

L2: H ----------------------> 14 --------------------> 31 -> nil
L1: H -------> 3 ------> 7 -> 14 -------> 22 -------> 31 -> nil
L0: H -> 1 -> 3 -> 4 -> 7 -> 9 -> 12 -> 14 -> 19 -> 22 -> 25 -> 31 -> nil

Now a search for 22 walks L2 to 14, drops to L1 at 14, walks to 22, done.

That is the entire idea. The shape of the structure is decided by coin flips at insert time; the search algorithm is "go right as long as you can, drop down when you must."

Why randomness instead of rebalancing¶

A balanced BST (AVL, red-black) maintains its O(log n) cost by rebalancing — rotations that fix invariants after every insert and delete. Rebalancing is local but tricky, and especially tricky under concurrency, because a rotation rewrites a triangle of three pointers and at least two parent pointers in one atomic step.

A skip list achieves the same expected cost without ever rebalancing. The probabilistic structure self-organises: roughly half the keys live at level 1, a quarter at level 2, and so on. There is no rebalancing because randomness already gives the balance — in expectation. The worst case (every key promoted to the max height) is astronomically unlikely; the variance is small enough to be invisible at n ≥ 1000.

That single property — no rotation — is why every concurrent ordered data structure published since 2001 has been either a skip list or a B-tree variant designed to avoid rotations.

The promotion probability p¶

Each node's height is 1 + (number of successful coin flips). With probability p, you "promote" to the next level. With probability 1 - p, you stop. The expected height is 1 / (1 - p). For p = 1/2, expected height is 2. For p = 1/4, it is 4/3 ≈ 1.33.

The smaller p, the fewer pointers per node (better memory), but the higher the constant factor on search (more nodes per level). p = 1/2 is the textbook default and what skipset uses. p = 1/4 is what java.util.concurrent.ConcurrentSkipListMap uses, on the grounds that the slightly slower searches are offset by smaller cache footprint.

MaxLevel¶

There must be a hard cap. With p = 1/2 and an expected N keys, the right cap is log2(N). For N ≤ 2^32 you need 32 levels. Picking MaxLevel = 32 and p = 1/2 is the standard configuration in practice. If you go higher, you waste a pointer per level on the head sentinel; if you go lower, you risk degraded search performance at very large n.

The head sentinel¶

A search always starts from the highest occupied level of a single permanent node called the head sentinel. The sentinel has MaxLevel next-pointers, all initially pointing to nil. Every insert may modify the sentinel's pointers if the new node's height exceeds any existing height. Having a sentinel removes special-case code at the boundary of the list.

What "concurrent" adds¶

A concurrent skip list must answer three questions for every operation:

1. Visibility. When goroutine A inserts a key, when does goroutine B see it?
2. Atomicity. A node with height h needs h next-pointers linked into the structure. Are all of them visible at once, or can a reader see a half-linked node?
3. Reclamation. When a node is deleted, when is it safe to free its memory?

In Go, the memory model and the garbage collector make question 3 easy compared to C++: the GC will not collect a node while any reader still holds a pointer to it. But questions 1 and 2 still demand care, and the rest of this section sketches the three strategies in increasing complexity.

Strategy A — Coarse-grained mutex (junior, this file)¶

Wrap the sequential skip list in sync.Mutex. Every operation Locks, does its work, Unlocks. Correct. Trivial. Slow.

type SkipList struct {
    mu  sync.Mutex
    sl  *seqSkipList
}

func (s *SkipList) Insert(k int) {
    s.mu.Lock()
    defer s.mu.Unlock()
    s.sl.insert(k)
}

If your workload is dominated by reads, swap Mutex for RWMutex and use RLock in Contains. That is still coarse but already much better for read-heavy traffic.

Strategy B — Fine-grained (per-node) locks (middle.md)¶

Each node has its own mutex. An insert locks just the predecessors at each level it needs to splice into. A delete locks the victim and its predecessors. Two unrelated inserts at opposite ends of the list never block each other.

Strategy C — Lock-free (senior.md)¶

No mutexes anywhere. Inserts walk the list, find predecessors and successors, then CAS each level's predecessor's next pointer from "old successor" to "new node." A failed CAS means another goroutine got there first; restart the search. Deletes are tricky because unlinking a single node from a level requires two atomic steps: first mark the node as deleted, then unlink it. The mark prevents lost updates if another goroutine is inserting a node right after it.

You will not write a lock-free skip list at the junior level. But you should know the names and rough shape — they are why this topic is interesting.

Skip list vs sync.Map, vs map+mutex, vs B-tree¶

The skip list wins when you need both ordering and concurrent writers. If you do not need ordering, sync.Map or map+RWMutex is faster and simpler. If you need ordering but writes are rare, a sorted slice protected by RWMutex is hard to beat.

Real-World Analogies¶

The express subway¶

Imagine the New York City subway. The 1 train (local) stops at every station — Christopher Street, Houston, Canal, Franklin, Chambers, Park Place, Cortlandt, Rector, South Ferry. That is level 0. The 2/3 train (express) stops at fewer stations: Chambers, Fulton, Wall, South Ferry. That is level 1. If you wanted to go from 96th Street to Wall Street, you ride the express most of the way and transfer to the local only for the last segment. A skip list is exactly that — express lanes that skip over most stops, and a base lane you transfer down to when you need to be precise.

The phone book with tabs¶

An old paper phone book has alphabetic tabs sticking out from the edge: A, B, C, ..., Z. You flip to the right tab, then scan inside that tab to find the name. The tabs are level 1, the names are level 0. A skip list generalises this to many tab-layers — A–C tabs, then A tabs, then names — and decides the tabs probabilistically rather than by alphabet.

The bookmark stack¶

Imagine you have a long sorted list of names in a Google Doc and you keep many bookmarks placed at evenly-spaced intervals. The top-level bookmarks are coarse (every 1000 names), the next level is finer (every 100), the next finer (every 10), and the bottom is every name. Searching is "jump to the nearest top-level bookmark before the target, then refine downwards." That refinement is exactly the skip-list drop-down.

The four-way intersection of highway exits¶

A long highway has exits numbered 1 through 1000. From a helicopter you can see the whole highway, but on the ground you can only see the next exit. To get to exit 472 from exit 0, you would not drive past every exit on the local road. You would take the interstate-skip: jump 100 exits to 100, jump 100 to 200, jump 100 to 300, jump 100 to 400, then jump 10 to 410, jump 10 to 420, ..., then jump 1 to 472. Each "jump level" is a layer in a skip list; you spend O(log) jumps overall.

The library catalogue cards¶

A traditional library catalogue has drawers labelled by ranges: A–B, C–F, G–J, ..., U–Z. Inside each drawer, cards are sorted alphabetically. To find "Knuth," you skip to the K–M drawer, then page through to "Knuth." The drawer ranges are level-1 nodes; the cards are level-0. A real catalogue often had drawer-of-drawers indexes too (the rare-collection room next door), giving level 2. Same idea.

In a 100-story building, you might have express elevators serving floors 0, 20, 40, 60, 80, 100; mid-express elevators serving every 5 floors; local elevators serving every floor. To reach floor 73, you ride the express to 60, switch to mid at 60, switch to local at 70. Each transfer corresponds to a "drop down" in a skip list search.

Mental Models¶

"Go right while you can, drop down when you must"¶

The entire search algorithm is one sentence. From the head, at the top level: if the next key is less than the target, move right; otherwise drop down one level. Repeat. Stop at level 0. The final position is either the target, or the first key greater than the target.

"A skip list is a deterministic tree with randomised branching"¶

If you squint, level i nodes are interior nodes; level 0 nodes are leaves. A node of height h has children at lower levels in the same column. The drop-down at search time is exactly tree descent. The difference from a B-tree is that the branching is random and per-key rather than balanced and per-page.

"Insert is search + splice; delete is search + unlink"¶

Both operations begin with the same search, recording the predecessor at every level — call this array update[] of length MaxLevel. Then:

• Insert: allocate a new node of randomly-chosen height; for each level i from 0 to height-1, set new.next[i] = update[i].next[i] and update[i].next[i] = new.
• Delete: for each level i from 0 to victim.height-1, set update[i].next[i] = victim.next[i].

In single-threaded code, both can be done in a tight inner loop without surprises. The whole game in concurrent code is that the update[] array is a snapshot of the structure that may be stale by the time you try to splice or unlink.

"Concurrency strategies grow in three big steps"¶

It really is three discrete jumps:

1. One mutex — easy to write, gives serial throughput.
2. One mutex per node + validate-then-link — much more code, much higher throughput, but still blocks under heavy contention on the head sentinel and on hot keys.
3. Lock-free with markers + CAS — much more code again, near-linear scalability under most workloads, but requires deep familiarity with the Go memory model.

Each step is roughly 3× more code than the previous, and 2–10× more throughput.

"Markers are the single hardest concept"¶

The reason most people fail to implement a lock-free skip list correctly is the marker node. It is a distinguished node whose presence in the chain says "the previous node is logically deleted." Without markers, a concurrent insert can attach itself to a node that is being unlinked, and the insert is then lost. Junior-level you should know the term. Senior-level you should write the marker logic. Professional-level you should prove it linearisable.

Pros and Cons¶

Pros¶

• Ordered. You get Min, Max, Range(lo, hi), and ordered iteration for free.
• Predictable cost. O(log n) expected for all three operations; no O(n) worst case (except astronomically unlikely promotions).
• No rebalancing. Massive simplification for concurrent implementations.
• Cache-okay. Linked structure, but each level's hop tends to bring contiguous pointers into cache.
• Mature libraries. skipset (Go), ConcurrentSkipListMap (Java), Folly (C++), RocksDB memtable (C++) all field-tested at scale.
• Composable. Easy to add features like multi-version concurrency control (MVCC) or snapshot iterators (each iterator captures a "view" of the structure at start time).

Cons¶

• Memory overhead per key. Each node carries h pointers (h averages 2 with p = 1/2). For 64-bit pointers that is ~16 bytes per key just for the structure, plus key/value size and Go header overhead.
• Pointer-chasing. Each level hop is a cache miss in the worst case. A B+tree's contiguous pages can outperform a skip list on dense, scan-heavy workloads.
• Probabilistic. Costs are expected, not worst-case. For latency-critical systems (real-time bidding, low-latency trading) the variance may matter.
• Random number cost. Naively calling math/rand.Intn per insert is slow and contested under concurrency. Production implementations use per-goroutine fast PRNGs.
• Hard to make truly lock-free in Go. Go's memory model lets you write CAS code (sync/atomic.CompareAndSwapPointer), but Go's unsafe.Pointer ergonomics make it easy to break. Libraries exist for a reason.
• Reclamation requires care in non-GC languages. Go's GC removes one whole category of bugs, but in C/C++ you need hazard pointers or epoch-based reclamation.

Use Cases¶

LSM-tree memtable¶

LevelDB, RocksDB, BadgerDB, Pebble (Cockroach Labs), and InfluxDB all use a concurrent skip list as the in-memory write buffer (memtable). When the memtable fills, it is flushed to an SSTable on disk. The skip list is chosen because writes need to be sorted by key for the on-disk file format, and the structure must support concurrent writers (one per gRPC handler / SQL session) without lock contention.

Sorted set in Redis¶

The Redis ZSET (sorted set) data type is implemented as a combination of a skip list and a hash map, exactly so that ZRANGEBYSCORE and ZRANGEBYRANK can be O(log n). The skip list keeps the score order; the hash map gives O(1) member existence. Redis is single-threaded so this implementation is not "concurrent" in the strict sense, but the structure choice is the same as what you would use in Go.

Priority queue with peek-by-key¶

When you need a priority queue but also need O(log n) deletion by arbitrary key (not just Pop the min), the standard container/heap is awkward — heap deletion by key is O(n). A skip list ordered by priority gives both Min() and DeleteByKey(k) in O(log n).

Time-series buffer¶

If you ingest events tagged with monotonic timestamps and need to compute count between t1 and t2 at query time, a skip list keyed by timestamp gives you the count via two searches in O(log n + result).

Concurrent ordered cache¶

If you need a cache that supports RangeBefore(key) (everything older than this), a skip list is more natural than a hash-based LRU. Several proprietary CDN and ad-tech systems use skip lists for this reason.

When not to use one¶

• If you do not need order, use sync.Map or map+RWMutex. They are 2–5× faster for pure point-lookup workloads.
• If your dataset is mostly read-only and built once, use a sorted slice with sort.Search. It is the smallest and fastest option.
• If your keys are integers in a known small range, use a []V indexed by key.

Code Examples¶

All examples below are single-threaded or use coarse locking. The fine-grained and lock-free versions live in middle.md and senior.md.

Example 1 — Minimal sequential skip list¶

package skip

import (
    "math/rand"
)

const (
    maxLevel = 16
    pNum     = 1 // probability numerator
    pDen     = 2 // probability denominator, so p = 1/2
)

type node struct {
    key  int
    next []*node // length == node's height
}

type SkipList struct {
    head  *node
    level int // current highest level in use
    rng   *rand.Rand
}

func New() *SkipList {
    return &SkipList{
        head:  &node{next: make([]*node, maxLevel)},
        level: 1,
        rng:   rand.New(rand.NewSource(1)),
    }
}

func (s *SkipList) randomHeight() int {
    h := 1
    for h < maxLevel && s.rng.Intn(pDen) < pNum {
        h++
    }
    return h
}

// Contains returns true if key is in the list.
func (s *SkipList) Contains(key int) bool {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
    }
    x = x.next[0]
    return x != nil && x.key == key
}

// Insert inserts key. Returns true if the key was new.
func (s *SkipList) Insert(key int) bool {
    update := make([]*node, maxLevel)
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
        update[i] = x
    }
    if x.next[0] != nil && x.next[0].key == key {
        return false // already present
    }
    h := s.randomHeight()
    if h > s.level {
        for i := s.level; i < h; i++ {
            update[i] = s.head
        }
        s.level = h
    }
    n := &node{key: key, next: make([]*node, h)}
    for i := 0; i < h; i++ {
        n.next[i] = update[i].next[i]
        update[i].next[i] = n
    }
    return true
}

// Delete removes key. Returns true if the key was present.
func (s *SkipList) Delete(key int) bool {
    update := make([]*node, maxLevel)
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
        update[i] = x
    }
    x = x.next[0]
    if x == nil || x.key != key {
        return false
    }
    for i := 0; i < len(x.next); i++ {
        if update[i].next[i] == x {
            update[i].next[i] = x.next[i]
        }
    }
    // Shrink level if top is empty.
    for s.level > 1 && s.head.next[s.level-1] == nil {
        s.level--
    }
    return true
}

A complete, working sequential skip list in fewer than 80 lines. Read every line slowly. Spend an hour drawing the structure on paper as keys arrive — that exercise pays off later.

Example 2 — Coarse-locked concurrent skip list¶

package skip

import "sync"

type ConcurrentSkipList struct {
    mu sync.RWMutex
    sl *SkipList
}

func NewConcurrent() *ConcurrentSkipList {
    return &ConcurrentSkipList{sl: New()}
}

func (c *ConcurrentSkipList) Contains(key int) bool {
    c.mu.RLock()
    defer c.mu.RUnlock()
    return c.sl.Contains(key)
}

func (c *ConcurrentSkipList) Insert(key int) bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.sl.Insert(key)
}

func (c *ConcurrentSkipList) Delete(key int) bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.sl.Delete(key)
}

That is the entire junior-level "concurrent" implementation. It is safe for any number of concurrent goroutines, but throughput is bounded by the throughput of one goroutine because every writer holds the exclusive lock. For read-heavy workloads the RWMutex is a 10–50× win over a plain Mutex. For write-heavy workloads you must move to per-node locking.

Example 3 — Driver that exercises it¶

package main

import (
    "fmt"
    "sync"

    "example.com/skip"
)

func main() {
    sl := skip.NewConcurrent()
    var wg sync.WaitGroup
    for i := 0; i < 8; i++ {
        wg.Add(1)
        go func(base int) {
            defer wg.Done()
            for k := 0; k < 1000; k++ {
                sl.Insert(base*1000 + k)
            }
        }(i)
    }
    wg.Wait()

    found := 0
    for k := 0; k < 8000; k++ {
        if sl.Contains(k) {
            found++
        }
    }
    fmt.Println("found:", found) // 8000
}

Run with go run -race to confirm there are no data races. (There will not be, because the mutex serialises everything.)

Example 4 — Range iteration¶

// Range calls f(key) for every key in [lo, hi). Stops if f returns false.
func (s *SkipList) Range(lo, hi int, f func(int) bool) {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < lo {
            x = x.next[i]
        }
    }
    x = x.next[0]
    for x != nil && x.key < hi {
        if !f(x.key) {
            return
        }
        x = x.next[0]
    }
}

After the search, a forward range scan is just a walk along level 0. That walk is the killer feature versus sync.Map. For one million keys, scanning a range of 1000 takes ~10 microseconds in a skip list and is impossible in sync.Map without iterating all million entries.

Example 5 — Storing values, not just keys¶

type kvNode struct {
    key  int
    val  string
    next []*kvNode
}

type KVSkipList struct {
    head  *kvNode
    level int
    rng   *rand.Rand
}

func (s *KVSkipList) Get(key int) (string, bool) {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
    }
    x = x.next[0]
    if x != nil && x.key == key {
        return x.val, true
    }
    return "", false
}

func (s *KVSkipList) Set(key int, val string) {
    update := make([]*kvNode, maxLevel)
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
        update[i] = x
    }
    if x.next[0] != nil && x.next[0].key == key {
        x.next[0].val = val // update in place
        return
    }
    h := s.randomHeight()
    if h > s.level {
        for i := s.level; i < h; i++ {
            update[i] = s.head
        }
        s.level = h
    }
    n := &kvNode{key: key, val: val, next: make([]*kvNode, h)}
    for i := 0; i < h; i++ {
        n.next[i] = update[i].next[i]
        update[i].next[i] = n
    }
}

The key-only and key-value versions differ only in node fields and the duplicate handling. Both can be wrapped in a mutex for the coarse-concurrent version.

Example 6 — Using the skipset library¶

package main

import (
    "fmt"

    "github.com/zhangyunhao116/skipset"
)

func main() {
    s := skipset.NewInt()
    s.Add(3)
    s.Add(1)
    s.Add(4)
    s.Add(1)
    s.Add(5)

    fmt.Println("contains 4:", s.Contains(4)) // true
    s.Range(func(value int) bool {
        fmt.Println(value) // 1 3 4 5
        return true
    })
    s.Remove(3)
    fmt.Println("len:", s.Len()) // 3
}

For 95% of real-world Go uses, skipset is the right answer. It is lock-free, well-tested, and routinely benchmarked above sync.Map for ordered workloads. The point of writing your own is to understand the algorithm — not to ship hand-rolled code into production.

Example 7 — Generic skip list (Go 1.18+ generics)¶

package skip

import (
    "cmp"
    "math/rand"
)

type gnode[K cmp.Ordered, V any] struct {
    key  K
    val  V
    next []*gnode[K, V]
}

type Map[K cmp.Ordered, V any] struct {
    head  *gnode[K, V]
    level int
    rng   *rand.Rand
}

func NewMap[K cmp.Ordered, V any]() *Map[K, V] {
    return &Map[K, V]{
        head:  &gnode[K, V]{next: make([]*gnode[K, V], maxLevel)},
        level: 1,
        rng:   rand.New(rand.NewSource(1)),
    }
}

func (m *Map[K, V]) Get(key K) (V, bool) {
    x := m.head
    for i := m.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
    }
    x = x.next[0]
    var zero V
    if x != nil && x.key == key {
        return x.val, true
    }
    return zero, false
}

Generics let you reuse the same code for Map[int, string], Map[string, []byte], and so on.

Example 8 — Snapshot-friendly iteration (junior-safe)¶

func (c *ConcurrentSkipList) Snapshot() []int {
    c.mu.RLock()
    defer c.mu.RUnlock()
    var out []int
    c.sl.Range(0, intMax, func(k int) bool {
        out = append(out, k)
        return true
    })
    return out
}

This is a consistent snapshot only because we hold the read lock for the whole walk. In the fine-grained and lock-free versions, snapshots are harder — that is where senior-level techniques like "epoch-based snapshot iterators" enter the picture.

Example 9 — A trivial benchmark¶

package skip

import (
    "math/rand"
    "testing"
)

func BenchmarkInsert(b *testing.B) {
    s := New()
    keys := rand.Perm(b.N)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s.Insert(keys[i])
    }
}

func BenchmarkContains(b *testing.B) {
    s := New()
    n := 1 << 20
    for i := 0; i < n; i++ {
        s.Insert(i)
    }
    keys := rand.Perm(n)
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        s.Contains(keys[i%n])
    }
}

Run with go test -bench .. On a 2024-era laptop you should see roughly 200–500 ns per Insert and 100–300 ns per Contains at one million keys.

Example 10a — Counting operations along a search¶

Add an integer counter inside the search loop and observe expected vs actual hops:

func (s *SkipList) ContainsCount(key int) (bool, int) {
    hops := 0
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
            hops++
        }
    }
    x = x.next[0]
    hops++
    return x != nil && x.key == key, hops
}

// In a test:
func TestExpectedHops(t *testing.T) {
    s := New()
    for i := 0; i < 1<<20; i++ {
        s.Insert(i)
    }
    rng := rand.New(rand.NewSource(1))
    var totalHops int
    const trials = 10000
    for i := 0; i < trials; i++ {
        _, h := s.ContainsCount(rng.Intn(1 << 20))
        totalHops += h
    }
    avg := float64(totalHops) / float64(trials)
    t.Logf("avg hops = %.1f (expected ~%.1f)", avg, 2*float64(20))
}

Observing the empirical average match the prediction 2 × log2(n) is the single best way to convince yourself the analysis is right.

Example 10 — Comparison harness (skip list vs sync.Map)¶

package skip_test

import (
    "math/rand"
    "sync"
    "testing"

    "example.com/skip"
)

func BenchmarkSkipListConcurrent(b *testing.B) {
    s := skip.NewConcurrent()
    b.RunParallel(func(pb *testing.PB) {
        rng := rand.New(rand.NewSource(rand.Int63()))
        for pb.Next() {
            k := rng.Intn(1 << 20)
            s.Insert(k)
            s.Contains(k)
        }
    })
}

func BenchmarkSyncMapConcurrent(b *testing.B) {
    var s sync.Map
    b.RunParallel(func(pb *testing.PB) {
        rng := rand.New(rand.NewSource(rand.Int63()))
        for pb.Next() {
            k := rng.Intn(1 << 20)
            s.Store(k, true)
            _, _ = s.Load(k)
        }
    })
}

You will see sync.Map decisively wins this unordered benchmark because it is hash-based and our concurrent skip list is still coarse-locked. The comparison flips for ordered workloads (range scans) and for skipset (lock-free, not the toy here).

Example 11 — A first-pass Min and Max¶

// Min returns the smallest key, or (0, false) if empty.
func (s *SkipList) Min() (int, bool) {
    if s.head.next[0] == nil {
        return 0, false
    }
    return s.head.next[0].key, true
}

// Max returns the largest key, or (0, false) if empty.
// Naive O(n) walk on L0; production code keeps a tail pointer or descends
// from the top level rightwards.
func (s *SkipList) Max() (int, bool) {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil {
            x = x.next[i]
        }
    }
    if x == s.head {
        return 0, false
    }
    return x.key, true
}

Min is O(1). Max here is O(n) walking level 0 because we have no tail sentinel; with a tail sentinel and a top-down right-walk, it becomes O(log n). Either way, Min is a strict win over hash maps (which would need an O(n) scan).

Example 12 — Floor and Ceiling¶

These are bread-and-butter ordered-set operations.

// Floor returns the largest key <= target. Returns (0, false) if no such key.
func (s *SkipList) Floor(target int) (int, bool) {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key <= target {
            x = x.next[i]
        }
    }
    if x == s.head {
        return 0, false
    }
    return x.key, true
}

// Ceiling returns the smallest key >= target.
func (s *SkipList) Ceiling(target int) (int, bool) {
    x := s.head
    for i := s.level - 1; i >= 0; i-- {
        for x.next[i] != nil && x.next[i].key < target {
            x = x.next[i]
        }
    }
    if x.next[0] == nil {
        return 0, false
    }
    return x.next[0].key, true
}

Note the subtle difference: Floor uses <=, Ceiling uses <. That difference is one of the most common off-by-one bugs in beginner skip list code.

Example 13 — Iterator pattern (Go-idiomatic)¶

// Iterator yields keys in ascending order. Safe only while holding the read
// lock on a ConcurrentSkipList (in the coarse-locked version).
type Iterator struct {
    cur *node
}

func (s *SkipList) Iterator() *Iterator {
    return &Iterator{cur: s.head}
}

func (it *Iterator) Next() (int, bool) {
    if it.cur.next[0] == nil {
        return 0, false
    }
    it.cur = it.cur.next[0]
    return it.cur.key, true
}

func (it *Iterator) Seek(target int) {
    x := it.cur
    if x == nil {
        return
    }
    // Restart from head for simplicity.
    it.cur = nil
}

Iterators in concurrent skip lists are subtle; this junior version is intentionally minimal. The full design with snapshot semantics lives in senior.md.

Example 14 — Plain Set API as a thin wrapper¶

// Set is a key-only concurrent set.
type Set struct {
    csl *ConcurrentSkipList
}

func NewSet() *Set                  { return &Set{csl: NewConcurrent()} }
func (s *Set) Add(k int) bool       { return s.csl.Insert(k) }
func (s *Set) Remove(k int) bool    { return s.csl.Delete(k) }
func (s *Set) Has(k int) bool       { return s.csl.Contains(k) }
func (s *Set) Each(f func(int)) {
    s.csl.mu.RLock()
    defer s.csl.mu.RUnlock()
    s.csl.sl.Range(intMin, intMax, func(k int) bool { f(k); return true })
}

This is the public API most callers actually want; the skip list is the implementation detail underneath.

Coding Patterns¶

Pattern 1 — "Find predecessors once, use them twice"¶

Both Insert and Delete start by walking the structure top-down and recording the predecessor at every level. That single pass is the cost; the actual splice or unlink is O(height) pointer assignments. Do not write two passes when one will do.

// Search and record predecessors.
for i := level - 1; i >= 0; i-- {
    for x.next[i] != nil && x.next[i].key < key {
        x = x.next[i]
    }
    update[i] = x
}
// Then either splice or unlink using update[].

Pattern 2 — Sentinel at the head, nil at the tail¶

Use a single permanent head node with MaxLevel next-pointers. Use nil to mean "end of list" at every level. This removes special cases for "inserting before everything" and "inserting after everything."

Pattern 3 — Per-iteration rng, not a package-level rand¶

math/rand.Intn from the package-level source has a mutex inside; calling it from many goroutines serialises them. Give each SkipList its own *rand.Rand (sequential case) or use math/rand/v2 with rand.Uint64 from a per-goroutine PCG source (concurrent case).

Pattern 4 — Choose height first, allocate node after¶

h := s.randomHeight()
n := &node{key: key, next: make([]*node, h)}

Knowing h before allocating saves an allocation and a copy. It also keeps the inner loop tight.

Pattern 5 — Update s.level only when needed¶

If your new node's height exceeds the current s.level, fill update[i] = s.head for the new levels before splicing, then bump s.level. Symmetrically, after Delete, decrement s.level while s.head.next[s.level-1] == nil.

Pattern 6 — Wrap before exposing¶

If you write a SkipList for testing and later want concurrency, do not retrofit locks into the same struct. Build the sequential SkipList clean, then write a thin ConcurrentSkipList{mu, sl} wrapper. Easier to test, easier to swap with a lock-free version later.

Pattern 7 — Pre-allocate the update[] array¶

Inside hot inner loops, allocate update once and reuse it. Or use a local var update [maxLevel]*node on the stack to avoid the heap entirely.

var update [maxLevel]*node
// ... fill update[i] = x in the search loop

This single trick can shave 50 ns per operation in tight benchmarks.

Pattern 8 — Probe with Contains before Insert only if duplicates are rare¶

Insert already does the search. Calling Contains first doubles the work. Trust your Insert to return bool for "was new."

Pattern 9 — Always test with the race detector¶

For any concurrent code, including the coarse-locked version: go test -race. The race detector is your friend; it catches missing locks, half-published pointers, and the captured-loop-variable bug. Running benchmarks under -race is slow but useful for the first few runs.

Pattern 9b — Maintain a length counter¶

Walking the structure to count elements is O(n). Maintain a counter and update it inside Insert and Delete:

type SkipList struct {
    head   *node
    level  int
    length int // updated only on successful Insert/Delete
    rng    *rand.Rand
}

func (s *SkipList) Len() int { return s.length }

In the coarse-locked wrapper, the counter is protected by the same mutex; in the lock-free version, use sync/atomic.AddInt64.

Pattern 9c — Returning (value, ok) from Get¶

Go's idiomatic two-return for maps is (value, found). Skip list Get should follow the same convention; do not return a zero-value V ambiguously.

func (m *KVSkipList) Get(key int) (val string, ok bool) {
    ...
}

Pattern 9d — Use named return values for clarity¶

func (s *SkipList) Insert(key int) (inserted bool) {
    ...
}

Helps readers; helps godoc. Optional but worth it on public APIs.

Pattern 10 — Keep Key Ordered¶

Use Go 1.21+ cmp.Ordered constraint when you generic. It is cleaner than a Less func(a, b K) bool callback and matches Go conventions.

Clean Code¶

Name the levels consistently¶

Pick one name and stick to it. Either level (Pugh) or height (Sedgewick) — never both for the same thing. A widely used split:

• s.level — the highest level currently occupied in the structure.
• n.height (= len(n.next)) — how tall this specific node is.
• MaxLevel — the hard cap.

Avoid magic numbers¶

const (
    MaxLevel = 16          // tune for expected N
    P        = 0.5         // promotion probability
)

Do not bury 0.5 in code; future readers will not know what 0.5 means.

Make randomHeight a method¶

It depends on the skip list's rng. Do not let callers pass the height in — they will get it wrong.

Keep Insert returning bool for "was new"¶

Standard convention. Java's Set.add and Python's set.add follow it. Saves callers a second probe.

Document the contract of Range¶

// Range invokes f for every key in [lo, hi), in ascending order.
// Range stops if f returns false. f must not call Insert or Delete on s.

Calling Insert/Delete from inside an in-progress Range deserves its own concurrency story (see senior.md). Just forbid it at the junior level.

Separate concurrency wrapper from algorithm¶

SkipList is the algorithm. ConcurrentSkipList is the wrapper. Reviewers can audit each in isolation.

Use defer for Unlock¶

c.mu.Lock()
defer c.mu.Unlock()

Always. Saves a missed unlock on panic. The defer cost is ~30 ns and irrelevant for skip list operations that take 500+ ns.

Comment the algorithm, not the syntax¶

// Search starts at the top level of the head sentinel and descends.
// At each level, walk right while next.key < key. This invariant means
// that on exit at level 0, x.next is either nil or x.next.key >= key.
for i := level - 1; i >= 0; i-- { ... }

A reader who knows Go does not need for i to be the level index. They need to know the algorithm's invariants.

Reject keys that violate ordering¶

For integer keys this is automatic. For []byte keys, document that "the slice contents must not be mutated after Insert." A mutated key breaks the structure silently.

Product Use and Feature¶

Where skip lists hide inside products¶

• CockroachDB / Pebble. Their memtable is a concurrent skip list. Every SQL INSERT flows through it. Pebble's skip list implementation is one of the most carefully tuned in Go.
• InfluxDB. Same story for the in-memory write buffer.
• Bigtable / HBase memstore. Originally a ConcurrentSkipListMap (Java).
• Redis ZSET. Skip list plus hash.
• MongoDB tailable cursor index. Internal use of skip-list-like ordered indexes.
• Discord's message store. Cassandra under the hood uses skip-list memtables.

If you are building any system whose write path is "ingest, sort, flush, query a range" — billing events, time-series, log records — a concurrent skip list is the standard answer.

A second product walkthrough — leaderboard¶

A multiplayer game wants a real-time leaderboard: each match end submits a (score, playerID) event; the top-100 scores are displayed in the lobby and refreshed every second.

type LeaderboardEntry struct {
    score    int64
    playerID string
}

type Leaderboard struct {
    sl     *ConcurrentSkipList // ordered by score
    scores sync.Map            // playerID -> current best score
}

func (l *Leaderboard) Submit(player string, score int64) {
    if prev, ok := l.scores.Load(player); ok && prev.(int64) >= score {
        return // no improvement
    }
    if prev, ok := l.scores.Swap(player, score); ok {
        l.sl.Delete(int(prev.(int64))) // remove old score
    }
    l.sl.Insert(int(score))
}

func (l *Leaderboard) Top(n int) []int64 {
    out := make([]int64, 0, n)
    l.sl.sl.Range(intMin, intMax, func(k int) bool {
        out = append(out, int64(k))
        return len(out) < n
    })
    // Reverse for descending order.
    for i, j := 0, len(out)-1; i < j; i, j = i+1, j-1 {
        out[i], out[j] = out[j], out[i]
    }
    return out
}

The skip list keeps the ordering; the sync.Map is the per-player index. The two together implement what Redis ZSET implements internally.

A third product walkthrough — rate-limit counters with TTL¶

type RateLimiter struct {
    sl *ConcurrentSkipList // keyed by request timestamp (nanoseconds)
}

func (r *RateLimiter) Allow(window time.Duration, limit int) bool {
    now := time.Now().UnixNano()
    cutoff := now - int64(window)
    // Count requests in the last window via Range; if below limit, accept.
    count := 0
    r.sl.sl.Range(int(cutoff), int(now+1), func(k int) bool {
        count++
        return count < limit
    })
    if count >= limit {
        return false
    }
    r.sl.Insert(int(now))
    // Optionally GC entries older than cutoff (run in a janitor goroutine).
    return true
}

For high-throughput rate limiters you would use Redis or a token bucket; the skip list version is the in-process answer for moderate scale.

Building a feature with a skip list¶

Suppose you want a "top-N online users by last-activity timestamp." Insert (timestamp, userID) on every activity; delete the old entry; Range(start, now) to query.

type Activity struct {
    timestamp int64
    userID    string
}

type ActivityIndex struct {
    sl     *ConcurrentSkipList // keyed by timestamp
    latest sync.Map            // userID -> latest timestamp
}

func (a *ActivityIndex) Touch(userID string) {
    now := time.Now().UnixNano()
    if prev, ok := a.latest.Load(userID); ok {
        a.sl.Delete(prev.(int64))
    }
    a.latest.Store(userID, now)
    a.sl.Insert(now)
}

func (a *ActivityIndex) RecentlyActive(window time.Duration) []int64 {
    cutoff := time.Now().Add(-window).UnixNano()
    var out []int64
    a.sl.sl.Range(cutoff, intMax, func(k int) bool {
        out = append(out, int64(k))
        return true
    })
    return out
}

This is a real shape; production systems do more (composite keys with (timestamp, userID) to avoid duplicate keys), but the structure is the same.

Tradeoffs in product use¶

• Latency p99 matters. Skip lists have variance; B-trees with bounded-height invariants have less. For latency-sensitive systems, run a histogram-aware benchmark on realistic data.
• Crash safety is separate. A skip list is in-memory. If you need crash safety, you either persist to a WAL (write-ahead log) before the in-memory insert (LSM pattern), or back it with bbolt / BoltDB (B+tree on mmap'd file).
• Memory pressure. Each node is ~64 bytes plus key/value. At 10M keys, that is ~640 MB. Below LRU eviction, above a sorted slice in code size.

Error Handling¶

Skip list operations themselves rarely "fail" in the recoverable sense. The errors are usage errors and panics.

Panics to expect¶

• Nil receiver. (*SkipList).Insert panics if s == nil. Always construct with New().
• Index out of range. Inside the inner loop only if level is set wrong; happens if you forget to bump s.level after a tall insert, or shrink past zero after deletes.
• make([]*node, 0). A node of height zero is meaningless; randomHeight must return >= 1. Off-by-one here panics on the next access.

Recoverable error cases¶

• Duplicate key on a set. Insert returns false. Caller decides whether that is OK.
• Key not found on Delete. Delete returns false. Often fine; sometimes a contract violation.
• Empty list Min(). Pick a contract: return (zero, false) for "not present," or panic. The Go convention is the former.

Always¶

• Guard public APIs with input validation if K is string or []byte and an empty value should be rejected.
• Document that the same key value should not be inserted twice if you only want a set; or use a Map wrapper that updates the value in place.

Security Considerations¶

The skip list itself has no I/O surface, but it sits on the critical path of larger systems and can be an attack vector through them.

Denial-of-service via worst-case heights¶

An adversary who can pick keys and somehow influence your PRNG could in principle craft inserts that all promote to MaxLevel. With p = 1/2 and a non-adversarial PRNG seed, the probability of a key reaching height h is 2^(-h); height 32 has probability 2^-32. With an adversarial seed, all bets are off.

• Mitigation: seed the PRNG with crypto/rand at startup, or use a hash of the key as part of the height derivation (so heights are deterministic in keys but not in user-supplied randomness).

Key-collision DoS¶

If keys are user-controlled hashes that an adversary chooses to be similar, the structure remains correct (it sorts) but range scans may be exploited. Pair with rate limiting at the API edge.

Memory exhaustion¶

A skip list has no built-in size cap. Insert in a hot loop with adversarial input and the process OOMs. Cap the size, or wrap the skip list in an LRU.

Concurrency bugs are security bugs¶

A race that corrupts the structure can promote any key to a different value, leading to authorization bypass. Always test concurrent skip list usage with go test -race.

Side-channel through timing¶

Contains returns in time proportional to log n. If you use it for secret keys (a session-token lookup), the timing reveals position in the structure. Use a constant-time hash map for secret tokens; the skip list is for ordered data, not for cryptographic lookups.

Performance Reference Numbers¶

Before tuning, know the rough ballpark.

These numbers are from a 2024 Apple M3 Pro at 4.05 GHz running Go 1.23 with GOGC=100. Your numbers will differ; always measure.

The key takeaway: even the lock-free variant pays maybe 30% more per single operation than the sequential one. The win comes from running many of them in parallel.

Performance Tips¶

Tip 1 — Pre-allocate update[] on the stack¶

var update [MaxLevel]*node

Saves the heap allocation in Insert and Delete. Worth ~50 ns each.

Tip 2 — Use unsafe.Slice (Go 1.20+) for node tails¶

Production skip lists store next as a tail-allocated array on the node struct, not as a separate slice. This removes one indirection per level hop and is a 10–20% win on benchmarks. Library code only; rolling your own with unsafe is error-prone.

Tip 3 — Tune MaxLevel to expected size¶

For n ≤ 100, MaxLevel = 7 is enough. For n ≤ 10^6, MaxLevel = 20. For n ≤ 10^9, MaxLevel = 30. A too-high MaxLevel wastes pointers in the head sentinel; a too-low one risks O(n) searches at the top end.

Tip 4 — Choose p¶

p = 1/2 minimises search hops; p = 1/4 halves average pointers per node at the cost of slightly more level walks. The right choice depends on cache size and key/value size. Default to p = 1/2.

Tip 5 — Random-number choice¶

math/rand is mutex-protected. math/rand/v2 is not, but you must hold the source yourself. For per-skip-list inserts in a single goroutine, the difference is invisible. For shared Insert from many goroutines, even after you make the structure lock-free, the RNG can become the bottleneck.

Tip 6 — Compare and switch keys¶

For numeric keys, comparison is one instruction. For string keys, profile the comparator. A skip list with a million 64-byte keys spends ~30% of Contains cost in bytes.Compare. Switching to a fixed-prefix comparator can be a win.

Tip 7 — Cache the most recent search position¶

If you Contains a key and the next call is for a nearby key, restarting from head wastes work. The "finger search" optimisation caches the previous endpoint; subsequent searches start there. Worth 2–5× on locality-heavy workloads.

Tip 8 — Avoid runtime.NumCPU shards prematurely¶

A common idea is to shard a skip list into N per-CPU lists. That is rarely a win for ordered data because Range across shards is O(N × log n). Only shard if you have measured contention and your queries are point-only.

Tip 9 — Read with RWMutex, not Mutex¶

If you stay coarse-locked, sync.RWMutex lets many Contains calls proceed in parallel. The reader cost is minimal but the throughput gain is huge for read-heavy traffic.

Tip 10 — Profile before tuning¶

go test -bench . -benchmem -cpuprofile cpu.out. Open with go tool pprof. The hot path is almost always inside the search loop; tune that first.

Best Practices¶

1. Start with skipset. Do not write your own concurrent skip list for production unless you have a benchmark-proven reason. Hand-rolled bugs are silent.
2. Test under -race. Every concurrent test, every time. The cost is irrelevant; the bug it catches is not.
3. Bound the size. Wrap with an LRU or with a manual flush trigger at Len() > N.
4. Snapshot for offline iteration. If a caller wants the full set, return a slice copy; do not lend a live iterator across goroutines.
5. Document the contract. "Concurrent skip list, lock-free, supports Insert, Delete, Contains, Range. Range iteration sees a consistent snapshot of keys present at the start of iteration. Inserts and deletes during iteration may or may not be visible."
6. Pick generics. Map[K cmp.Ordered, V any] beats untyped interface{} for performance and clarity.
7. Avoid copying. Always pass *SkipList by pointer; copying a skip list is meaningless and dangerous.
8. Avoid embedding. type MyThing struct { *SkipList } is tempting but exposes internal methods. Use a named field.
9. Use atomic counters for Len(). Counting on demand by walking is O(n). Maintain a counter under the mutex (junior) or via sync/atomic.AddInt64 (senior).
10. Choose your stable seed for tests. Random promotion makes outputs nondeterministic. Tests should use a fixed seed and assert structural invariants, not exact heights.

Edge Cases and Pitfalls¶

Pitfall 1 — Forgetting to bump s.level¶

if h > s.level {
    for i := s.level; i < h; i++ {
        update[i] = s.head
    }
    s.level = h
}

If you skip this block, your new tall node's upper levels are spliced behind a head whose update[i] slot was uninitialised (or pointing to an unrelated node). The search will then not find the key on future calls.

Pitfall 2 — update[i].next[i] != x on delete¶

If something concurrent has already moved x, your Delete will silently link the wrong nodes. In the coarse-locked version this cannot happen because the mutex serialises everything; but it is the first check you must add when moving to per-node locks.

Pitfall 3 — Mutating keys after insert¶

key := []byte("alice")
sl.Insert(key)
key[0] = 'b' // now sl thinks 'b' is at the position of 'a'

Skip lists assume keys are immutable. Document this loudly.

Pitfall 4 — Shared *rand.Rand across goroutines¶

*rand.Rand is not safe for concurrent use. If multiple goroutines insert simultaneously and share the same rng, you will see panics or duplicated values. Per-skiplist with a mutex (coarse) or per-goroutine sources (lock-free) both work.

Pitfall 5 — Comparison overflow¶

For 64-bit integer keys, a - b < 0 is not the same as a < b when b is math.MinInt64. Use < directly; the compiler turns it into a single comparison instruction.

Pitfall 6 — MaxLevel = 0 or negative¶

A typo here breaks the structure on the first insert. Use a const, not a parameter.

Pitfall 7 — Inserting nil key into a string-keyed list¶

"" and nil may be the same for some comparators and different for others. Decide and document.

Pitfall 8 — Garbage from Delete¶

After Delete, the unlinked node may still be referenced by a goroutine that started a search before the unlink. In Go, the GC keeps it alive until the last pointer drops. In C++ you would need hazard pointers. Do not "manually free" anything.

Pitfall 9 — Range deadlock with f that calls back¶

If f inside Range calls another method on the same skip list, the second method tries to acquire the lock the first call holds. Deadlock. Document the contract.

Pitfall 9b — Range with adversarial f¶

If f performs blocking I/O on each key (a network call, a database write), Range holds the read lock for the whole duration. Other writers wait. Always make f cheap, or copy keys to a slice under the lock and process outside.

Pitfall 9c — Confusing level with height¶

s.level is the current highest occupied level (1-indexed). n.height is the height of a specific node (equal to len(n.next)). Mix them up in a loop bound and you walk into garbage.

Pitfall 9d — Forgetting update is MaxLevel, not s.level¶

update := make([]*node, MaxLevel) // not s.level

If you size update to s.level, your tall new node's upper levels have no recorded predecessor.

Pitfall 9e — Capacity allocation in make([]*node, MaxLevel)¶

make([]*node, MaxLevel) allocates MaxLevel nil pointers — exactly what we want. Do not write make([]*node, 0, MaxLevel); that gives an empty slice and the indexed assignment update[i] = x panics.

Pitfall 10 — Forgetting that Range needs the read lock for the whole walk¶

If you take the lock, build a snapshot, drop the lock, then walk the snapshot — fine. If you take the lock, walk, and an Insert in between flips the structure — chaos. Hold the lock for the entire iteration in the coarse version.

Annotated Mistakes — Beginner Mistakes Caught in Code Review¶

A junior engineer's first PR with a hand-rolled skip list will typically have most of the following. Reviewer comments included.

// Mistake A
func (s *SkipList) Insert(key int) {
    update := []*node{}
    x := s.head
    for i := s.level; i >= 0; i-- {  // BUG: should be s.level - 1
        for x.next[i] != nil && x.next[i].key < key {
            x = x.next[i]
        }
        update = append(update, x)  // BUG: update is in reverse order
    }
    ...
}