Introduction

A lock-free skip list is a concurrent ordered set or map built from layered linked lists and atomic compare-and-swap operations instead of coarse locks. The core challenge is not basic skip-list search. It is making insert and delete correct while other threads are traversing or modifying the same structure. A practical implementation usually follows the well-known pattern of logical deletion first, then physical unlinking.

Start With the Right Node Structure

A concurrent skip-list node needs:

• a key
• a top level
• one next pointer per level
• a way to mark links during deletion

In Java, AtomicMarkableReference is a common building block:

1import java.util.concurrent.atomic.AtomicMarkableReference;
2
3final class Node {
4    final int key;
5    final int topLevel;
6    final AtomicMarkableReference<Node>[] next;
7
8    @SuppressWarnings("unchecked")
9    Node(int key, int topLevel) {
10        this.key = key;
11        this.topLevel = topLevel;
12        this.next = (AtomicMarkableReference<Node>[])
13            new AtomicMarkableReference[topLevel + 1];
14
15        for (int i = 0; i <= topLevel; i++) {
16            next[i] = new AtomicMarkableReference<>(null, false);
17        }
18    }
19}

The mark bit is critical. It lets one thread declare a link logically deleted before another thread physically unlinks it.

Use Head and Tail Sentinels

Most implementations add sentinel nodes for negative and positive infinity. That makes traversal logic simpler because every search starts from a well-defined top-left corner.

1final int MAX_LEVEL = 16;
2final Node head = new Node(Integer.MIN_VALUE, MAX_LEVEL);
3final Node tail = new Node(Integer.MAX_VALUE, MAX_LEVEL);
4
5{
6    for (int level = 0; level <= MAX_LEVEL; level++) {
7        head.next[level].set(tail, false);
8    }
9}

With this setup, every search can walk from head toward tail without null checks driving the whole algorithm.

The Search Routine Must Also Help With Cleanup

The heart of a lock-free skip list is a find method that returns predecessors and successors for every level. While traversing, it also notices marked nodes and helps unlink them.

1boolean find(int key, Node[] preds, Node[] succs) {
2    boolean[] marked = {false};
3    retry:
4    while (true) {
5        Node pred = head;
6        for (int level = MAX_LEVEL; level >= 0; level--) {
7            Node curr = pred.next[level].getReference();
8            while (true) {
9                Node succ = curr.next[level].get(marked);
10                while (marked[0]) {
11                    if (!pred.next[level].compareAndSet(curr, succ, false, false)) {
12                        continue retry;
13                    }
14                    curr = pred.next[level].getReference();
15                    succ = curr.next[level].get(marked);
16                }
17                if (curr.key < key) {
18                    pred = curr;
19                    curr = succ;
20                } else {
21                    break;
22                }
23            }
24            preds[level] = pred;
25            succs[level] = curr;
26        }
27        return succs[0].key == key;
28    }
29}

This "helping" behavior is what keeps the structure moving forward without central locking.

Insert Bottom-Up With CAS

Insertion typically works like this:

1. choose a random top level
2. call find
3. if the key already exists, stop
4. link level 0 first using CAS
5. link higher levels one by one

The bottom-level link linearizes the insertion. Higher levels can be retried until they succeed.

1boolean add(int key) {
2    int topLevel = randomLevel();
3    Node[] preds = new Node[MAX_LEVEL + 1];
4    Node[] succs = new Node[MAX_LEVEL + 1];
5
6    while (true) {
7        boolean found = find(key, preds, succs);
8        if (found) return false;
9
10        Node newNode = new Node(key, topLevel);
11        for (int level = 0; level <= topLevel; level++) {
12            newNode.next[level].set(succs[level], false);
13        }
14
15        if (!preds[0].next[0].compareAndSet(succs[0], newNode, false, false)) {
16            continue;
17        }
18
19        for (int level = 1; level <= topLevel; level++) {
20            while (!preds[level].next[level].compareAndSet(succs[level], newNode, false, false)) {
21                find(key, preds, succs);
22            }
23        }
24        return true;
25    }
26}

Delete by Marking, Then Unlinking

Deletion is usually split into two phases:

• logical deletion by marking next pointers
• physical removal by unlinking the node from predecessors

That split is what makes concurrent traversals safe. Once the bottom-level link is marked, the key is considered deleted even if higher-level cleanup is still happening.

This is much safer than trying to remove the node from all levels atomically in one impossible step.

Random Levels Still Matter

Even in the lock-free version, the skip list depends on random tower heights for expected logarithmic performance. The concurrency logic changes the pointer management, but not the probabilistic balancing idea.

The random-level generator does not need cryptographic quality. It just needs a reasonable geometric distribution.

Common Pitfalls

The biggest mistake is trying to write a "lock-free" skip list without a clear logical-deletion protocol. Another is forgetting that traversal must help clean up marked nodes or the structure accumulates garbage links and progress degrades. Memory reclamation is another hard problem in lower-level languages, because removed nodes may still be visible to racing readers. In Java, the garbage collector helps, but correctness is still subtle. Finally, a lock-free skip list is not a beginner data-structure project; if production correctness matters more than learning value, a battle-tested concurrent collection is often the better choice.

Summary

• A lock-free skip list uses atomic link updates instead of coarse locks.
• Nodes typically store per-level atomic next pointers with mark bits.
• 'find must both search and help unlink logically deleted nodes.'
• Insertions usually linearize at the bottom-level CAS.
• Deletions are typically logical first, physical second.
• If you need production reliability, prefer a mature concurrent implementation unless you truly need a custom one.