Skip List Visualization

Watch how Skip List uses probabilistic multi-level links for fast search

Skip List is a probabilistic data structure that allows O(log n) search, insert and delete operations. It uses multiple levels of linked lists where each higher level 'skips' more elements, similar to express lanes in a highway.

输入值并选择操作

Skip List Structure

  • Multiple levels of sorted linked lists
  • Bottom level contains all elements
  • Each higher level is a subset of the level below
  • Level promotion is determined by coin flips (probability)

Search Process

  1. Start from the top-left (highest level head)
  2. Move right until next element is greater than target
  3. Move down one level and repeat
  4. Continue until found or reach bottom level

Insert Process

  1. Find the position at each level (like search)
  2. Insert at level 0 (bottom)
  3. Flip a coin: heads = promote to next level
  4. Repeat coin flips until tails or max level
Operation Average Worst
Search O(log n) O(n)*
Insert O(log n) O(n)*
Delete O(log n) O(n)*

*Worst case is very rare due to probabilistic nature

Space Complexity: O(n) on average, O(n log n) worst case

Expected levels: O(log n) with p=0.5

Redis Sorted Sets

Redis uses Skip List for ZSET to support O(log n) range queries and score updates

LevelDB / RocksDB

Used in MemTable for in-memory sorted key-value storage

Concurrent Data Structures

Lock-free skip lists are easier to implement than lock-free balanced trees

Implementation

import random

class SkipListNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.level = 0
        self.head = SkipListNode(float('-inf'), max_level)
    
    def random_level(self):
        """Generate random level using coin flips"""
        level = 0
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level
    
    def search(self, key):
        """Search for a key in the skip list"""
        current = self.head
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.key == key
    
    def insert(self, key):
        """Insert a key into the skip list"""
        update = [None] * (self.max_level + 1)
        current = self.head
        
        # Find position at each level
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current
        
        # Determine level for new node
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.head
            self.level = new_level
        
        # Create and insert new node
        new_node = SkipListNode(key, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

# Usage
sl = SkipList(max_level=6, p=0.5)
for val in [3, 6, 7, 9, 12, 19, 21, 25]:
    sl.insert(val)
print(sl.search(19))  # True

import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    
    private int level;
    private SkipListNode head;
    private Random random;
    
    public SkipList() {
        this.level = 0;
        this.head = new SkipListNode(Integer.MIN_VALUE, MAX_LEVEL);
        this.random = new Random();
    }
    
    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
    public boolean search(int key) {
        SkipListNode current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key < key) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.key == key;
    }
    
    public void insert(int key) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = head;
        
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }
        
        SkipListNode newNode = new SkipListNode(key, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
    
    public static void main(String[] args) {
        SkipList sl = new SkipList();
        int[] values = {3, 6, 7, 9, 12, 19, 21, 25};
        for (int v : values) sl.insert(v);
        System.out.println(sl.search(19)); // true
    }
}

class SkipListNode {
    int key;
    SkipListNode[] forward;
    
    SkipListNode(int key, int level) {
        this.key = key;
        this.forward = new SkipListNode[level + 1];
    }
}