Java实现一个轻量的跳表demo

import java.util.Random;

public class SkipList {

    private final static int MAX_LEVEL = 16;

    private Node head = new Node(MAX_LEVEL, 0);
    private Random random = new Random();

    public Node search(int key) {
        Node cur = head;
        for(int level=MAX_LEVEL-1;level>=0;level--) {
            while(cur.forwards[level] != null && cur.forwards[level].key < key) {
                cur = cur.forwards[level];
            }
            if(cur.forwards[level] != null && cur.forwards[level].key == key) {
                return cur.forwards[level];
            }
        }
        return null;
    }

    public void insert(int key) {
        Node cur = head;
        int level = randomLevel();
        Node newNode = new Node(level, key);

        Node[] update = new Node[level];
        for(int i=0;i<level;i++) {
            update[i] = head;
        }

        for(int i=level-1;i>=0;i--) {
            while(cur.forwards[i] != null && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }

        for(int i=0;i<level;i++) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }
    }

    public void delete(int key) {
        Node cur = head;
        Node[] update = new Node[MAX_LEVEL];
        for(int i=MAX_LEVEL-1;i>=0;i--) {
            while(cur.forwards[i] != null && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            update[i] = cur;
        }

        if(cur.forwards[0] != null && cur.forwards[0].key == key) {
            for(int i=MAX_LEVEL-1;i>=0;i--) {
                if(update[i].forwards[i] != null && update[i].forwards[i].key == key) {
                    update[i].forwards[i] = update[i].forwards[i].forwards[i];
                }
            }
        }
    }

    private int randomLevel() {
        int level = 1;
        for(int i=1;i<MAX_LEVEL;i++) {
            if(random.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    public void print() {
        for(int level=MAX_LEVEL-1;level>=0;level--) {
            Node cur = head.forwards[level];
            System.out.print("Level " + (level+1) + ": ");
            while(cur != null) {
                System.out.print(cur.key+" ");
                cur = cur.forwards[level];
            }
            System.out.println();
        }
    }

    class Node {
        public int key;
        public Node[] forwards;

        public Node(int level, int key) {
            this.key = key;
            forwards = new Node[level];
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        skipList.insert(1);
        skipList.insert(4);
        skipList.insert(2);
        skipList.insert(3);
        skipList.print();
        skipList.delete(4);
        skipList.print();
        Node node = skipList.search(2);
        if(node != null) {
            System.out.println(node.key);
        }
    }
}