什么是跳表？

一、什么是跳表？

跳表其实就是多层链表，用来解决单层链表复杂度较高的问题。

跳表的特点：

• 多层链表组成
• 每一层链表都是有序的
• 最后一层链表包含所有数据
• 第二层链表开始包含前面层所有数据
• …

二、跳表操作

1、插入

跳表插入逻辑跟链表一样的是要找到插入节点的前一个节点即可，但不同的是跳表还要指向下层的节点，相关代码为：

public class SkipListNode {
    private int val;
    private SkipListNode next;
    private SkipListNode down;
}

另外跳表还会通过随机函数来获得一个随机值，来判断当前插入元素要从哪一层开始往下插入，相关代码为：

public class SkipList {
    /** 省略其他代码 **/
    private int randLevel() {
        // 节点越少的层级，随机概率越低
        // 1的概率是0.5，2的概率是0.25，3的概率是0.125...
        int level = 1;
        
        while (Math.random() < 0.5f && level < MAX_LEVEL) {
            level ++;
        }
        
        return level;
    }
}

插入步骤如下：

1.判断level层往上的层级有没有创建，没有的话则先创建，如图所示

2.找到待插入节点的前一个节点，连接next指针

3.类似步骤2，连接down指针

对应代码为：

public class SkipList {
    /** 省略其他代码 **/
    public void add(int num) {
        int level = randLevel();// 从第几层开始插入，随机数。
        // 记录待插入节点的前一个节点。
        SkipListNode[] preNodes = new SkipListNode[level];

        // 第一步：如果跳表层数比较少，在上面添加，层数至少为 level 。
        if (curLevelCount < level) {
            SkipListNode beforeHead = head;
            head = new SkipListNode(-1, null);// 更新 head 节点。
            SkipListNode curHead = head;
            // 在上面添加每层的头节点。
            for (int i = curLevelCount; i < level - 1; i++) {
                SkipListNode node = new SkipListNode(-1, null);
                curHead.down = node;
                curHead = node;
            }
            // 最后创建的链表头节点和之前的头节点连在一起。
            curHead.down = beforeHead;
        }

        // 第二步：从上往下查找每层待插入节点的前一个节点。
        SkipListNode pre = head;
        // 上层不需要插入的跳过。
        for (int i = curLevelCount - 1; i >= level; i--)
            pre = pre.down;
        // 从当前层往下每层都要插入该节点，找出每层待插入节点的前一个节点。
        for (int i = level - 1; i >= 0; i--) {
            while (pre.next != null && pre.next.val < num)
                pre = pre.next;
            preNodes[i] = pre;// 记录前一个节点。
            pre = pre.down;
        }

        // 第三步：节点插入，插入的时候不光有 next 指针，而且还有 down 指针。
        SkipListNode topNode = null;
        // 把新建节点 node 插到该层下面的每一层。
        for (int i = level - 1; i >= 0; i--) {
            // 创建新节点。
            SkipListNode node = new SkipListNode(num, preNodes[i].next);
            // 链表的插入，参见单向链表的插入。
            preNodes[i].next = node;
            // 上下也要连接。
            if (topNode != null)
                topNode.down = node;
            topNode = node;
        }
        if (level > curLevelCount)// 更新跳表的层级，用来记录当前跳表的层级。
            curLevelCount = level;
    }
}

2、查询

跳表查询从最上面一层开始，每层往后查找，如果后面没有了节点或者节点值比目标值大，则往下层查找，，如图所示：

对应代码为：

public class SkipList {
    /** 省略其他代码 **/
    // 查找值为 target 的节点。
    public boolean search(int target) {
        SkipListNode pre = head;
        while (pre != null) {
            // 如果当前节点值小于 target ，需要到右边查找，如果右边没有节点就到下边查找。
            if (pre.val < target) {
                if (pre.next == null)// 右边没有节点，到下边查找
                    pre = pre.down;
                else
                    pre = pre.next.val > target ? pre.down : pre.next;
            } else if (pre.val == target) {// 如果找到直接返回。
                return true;
            } else {
                return false;// 如果当前节点值大于 target ，说明没有，直接返回 false 。
            }
        }
        return false;
    }
}

3、删除

跳表删除跟跳表添加类似，从上到下每一层都找到待删除节点的前一个节点，删除后如果该层没有其他节点了，则需要删除该层

对应代码为：

public class SkipList {
    /** 省略其他代码 **/
    public boolean remove(int num) {
        // 删除链表和插入链表类似，都是需要先找到插入或删除链表的前一个节点。
        int topIndex = -1;// 从当前层开始往下每层都要删除。
        // 查找待删除节点的前一个节点，从上面一层开始查找。
        SkipListNode pre = head;
        for (int i = curLevelCount - 1; i >= 0; i--) {
            while (pre.next != null && pre.next.val < num)
                pre = pre.next;
            // 如果找到就终止查找，表示在当前层以及他下面的所有层都要删除该节点。
            if (pre.next != null && pre.next.val == num && topIndex == -1) {
                topIndex = i;
                break;
            }
            if (pre.down == null)// 如果跳表中没有要删除的节点，返回 false 。
                return false;
            pre = pre.down;// 当前层没找到就往下一层继续查找。
        }

        if (topIndex == -1)// 如果跳表中没找到要删除的节点，返回 false 。
            return false;

        // 从 topIndex 层开始，他下面的每一层都要删除。
        for (int i = topIndex; i >= 0; i--) {
            if (pre.next != null)// 节点删除，参考单向链表删除。
                pre.next = pre.next.next;
            pre = pre.down;// 继续下一层的删除。
            if (pre != null)// 找到待删除节点的前一个节点。
                while (pre.next != null && pre.next.val != num)
                    pre = pre.next;
        }
        // 如果上面一层的节点被删除完了，要更新 curLevelCount 的值 ，还要更新 head节点。
        SkipListNode cur = head;
        while (curLevelCount > 1 && cur.next == null) {
            cur = cur.down;
            head = cur;
            curLevelCount--;
        }
        return true;
    }
}