Redis必知必会之zset底层—Skip List跳跃列表（面试加分项）

package com.liziba.skiplist;
import java.util.Random;
/**
 * <p>
 *      跳表实现
 * </p>
 *
 * @Author: Liziba
 */
public class SkipList {
    /** 最上层头节点 */
    public Node head;
    /** 最上层尾节点 */
    public Node tail;
    /** 总层数 */
    public int level;
    /** 元素个数 */
    public int size;
    public Random random;
    public SkipList() {
        level = size = 0;
        head = new Node(null);
        tail = new Node(null);
        head.next = tail;
        tail.prev = head;
    }
    /**
     * 查询插入节点的前驱节点位置
     *
     * @param score
     * @return
     */
    public Node fidePervNode(Double score) {
        Node p = head;
        for(;;) {
            // 当前层(level)往后遍历，比较score，如果小于当前值，则往后遍历
            while (p.next.value == null && p.prev.score <= score)
                p = p.next;
            // 遍历最右节点的下一层(level)
            if (p.down != null)
                p = p.down;
            else
                break;
        }
        return p;
    }
    /**
     * 插入节点，插入位置为fidePervNode(Double score)前面
     *
     * @param score
     * @param value
     */
    public void insert(Double score, String value) {
        // 当前节点的前置节点
        Node preNode = fidePervNode(score);
        // 当前新插入的节点
        Node curNode = new Node(score, value);
        // 分数和值均相等则直接返回
        if (curNode.value != null && preNode.value != null && preNode.value.equals(curNode.value)
                  && curNode.score.equals(preNode.score)) {
            return;
        }
        preNode.next = curNode;
        preNode.next.prev = curNode;
        curNode.next = preNode.next;
        curNode.prev = preNode;
        int curLevel = 0;
        while (random.nextDouble() < 1/2) {
            // 插入节点层数(level)大于等于层数(level)，则新增一层(level)
            if (curLevel >= level) {
                Node newHead = new Node(null);
                Node newTail = new Node(null);
                newHead.next = newTail;
                newHead.down = head;
                newTail.prev = newHead;
                newTail.down = tail;
                head.up = newHead;
                tail.up = newTail;
                // 头尾节点指针修改为新的，确保head、tail指针一直是最上层的头尾节点
                head = newHead;
                tail = newTail;
                ++level;
            }
            while (preNode.up == null)
                preNode = preNode.prev;
            preNode = preNode.up;
            Node copy = new Node(null);
            copy.prev = preNode;
            copy.next = preNode.next;
            preNode.next.prev = copy;
            preNode.next = copy;
            copy.down = curNode;
            curNode.up = copy;
            curNode = copy;
            ++curLevel;
        }
        ++size;
    }
    /**
     * 查询指定score的节点元素
     * @param score
     * @return
     */
    public Node search(double score) {
        Node p = head;
        for (;;) {
            while (p.next.score != null && p.next.score <= score)
                p = p.next;
            if (p.down != null)
                p = p.down;
            else // 遍历到最底层
                if (p.score.equals(score))
                    return p;
                return null;
        }
    }
    /**
     * 升序输出Skip List中的元素 （默认升序存储，因此从列表head往tail遍历）
     */
    public void dumpAllAsc() {
        Node p = head;
        while (p.down != null) {
            p = p.down;
        }
        while (p.next.score != null) {
            System.out.println(p.next.score + "-->" + p.next.value);
            p = p.next;
        }
    }
    /**
     * 降序输出Skip List中的元素
     */
    public void dumpAllDesc() {
        Node p = tail;
        while (p.down != null) {
            p = p.down;
        }
        while (p.prev.score != null) {
            System.out.println(p.prev.score + "-->" + p.prev.value);
            p = p.prev;
        }
    }
    /**
     * 删除Skip List中的节点元素
     * @param score
     */
    public void delete(Double score) {
        Node p = search(score);
        while (p != null) {
            p.prev.next = p.next;
            p.next.prev = p.prev;
            p = p.up;
        }
    }
}