跳表实现

1. python

class Node:
        
    value = None
    levels = []

class Skiplist:

    def __init__(self):
        self.head = Node()
        self.max_level  = 500
        self.head.levels = [None for i in range(self.max_level)]
        self.currLevel = 1


    def search(self, target: int) -> bool:
        cu = self.head
        for i in range(self.currLevel-1, -1, -1):
            while cu.levels[i] and cu.levels[i].value < target:
                cu = cu.levels[i]
            if cu.levels[i] and cu.levels[i].value == target:
                return True
        return False


    def add(self, num: int) -> None:
       
        new_level = self.get_level()
        levels = [None for i in range(new_level)]
      
        insert_node = Node()
        insert_node.value = num
        insert_node.levels = levels

        cu = self.head
        for i in range(self.currLevel-1, -1, -1):
            while cu.levels[i] is not None and cu.levels[i].value < num:
                cu = cu.levels[i]
            if i > new_level - 1:
                continue
            if cu.levels[i] is None:
                cu.levels[i] = insert_node
            else:
                tmp = cu.levels[i]
                insert_node.levels[i] = tmp
                cu.levels[i] = insert_node
        
        if new_level > self.currLevel:
            for i in range(self.currLevel, new_level):
                self.head.levels[i] = insert_node
            self.currLevel = new_level


    def erase(self, num: int) -> bool:
        flag = False 
        cu = self.head
        for i in range(self.currLevel-1, -1, -1):
            while cu.levels[i] and cu.levels[i].value < num:
                cu = cu.levels[i]
            
            if cu.levels[i] and cu.levels[i].value == num:
                flag = True
                cu.levels[i] = cu.levels[i].levels[i]
                
        return flag

    def get_level(self):
        level = 1
        while random.random() < 0.25 and level < self.max_level:
            level = level + 1
        return level

2. java

public class Skiplist {


    static class Node {
        private Integer value;
        private Node[] nexts;

        public static Node init(Integer val, int level) {
            Node node = new Node();
            node.value = val;
            node.nexts = new Node[level];
            return node;
        }
    }

    private static final int MAX_LEVEL = 32;
    private final Node head;
    private int currLevel;

    public Skiplist() {
        this.head = Node.init(null, MAX_LEVEL);
        this.currLevel = 1;
    }

    public boolean search(int target) {
        Node cursor = this.head;
        for (int i = this.currLevel - 1; i >= 0; i--) {
            cursor = findClosest(cursor, i, target);
            if (cursor.nexts[i] != null && cursor.nexts[i].value == target) {
                return true;
            }
        }
        return false;
    }

    public void add(int num) {
        Node cursor = this.head;
        int newLevel = randomLevel();
        Node insert = Node.init(num, newLevel);
        for (int i = this.currLevel - 1; i >= 0; i--) {
            cursor = findClosest(cursor, i, num);
            if (i > (newLevel-1)) {
                continue;
            }
            if (cursor.nexts[i] == null) {
                cursor.nexts[i] = insert;
            } else {
                Node tmp = cursor.nexts[i];
                cursor.nexts[i] = insert;
                insert.nexts[i] = tmp;
            }
        }

        if (newLevel > currLevel) {
            for (int i = currLevel; i < newLevel; i++) {
                head.nexts[i] = insert;
            }
            currLevel = newLevel;
        }
    }

    public boolean erase(int num) {
        Node cursor = this.head;
        boolean erased = false;
        for (int i = this.currLevel - 1; i>=0; i--) {
            cursor = findClosest(cursor, i, num);
            if (cursor.nexts[i] != null && cursor.nexts[i].value == num) {
                cursor.nexts[i] = cursor.nexts[i].nexts[i];
                erased = true;
            }
        }
        return erased;
    }

    private int randomLevel() {
        int level = 1;
        while (Math.random() < 0.25 && level < MAX_LEVEL) {
            level += 1;
        }
        return level;
    }

    private Node findClosest(Node start, int levelIdx, int target) {
        while (start.nexts[levelIdx] != null && start.nexts[levelIdx].value < target) {
            start = start.nexts[levelIdx];
        }
        return start;
    }

    public static void main(String[] args) {
        Skiplist skiplist = new Skiplist();
        skiplist.add(1);
        skiplist.add(2);
        skiplist.add(3);
        System.out.println(skiplist.search(0));
        System.out.println(skiplist.erase(0));
        System.out.println(skiplist.search(1));
        System.out.println(skiplist.erase(1));
        System.out.println(skiplist.search(1));

    }


}