Skip List(跳跃列表) 它到底好在哪？今天我们不仅只聊为什么，还手写一个玩玩

2021 年 11 月 27 日
本文字数：11362 字
阅读完需：约 37 分钟

一、简介

跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

Skip List(跳跃列表)这种随机的数据结构，可以看做是一个二叉树的变种，它在性能上与红黑树、AVL 树很相近；但是 Skip List(跳跃列表)的实现相比前两者要简单很多，目前 Redis 的 zset 实现采用了 Skip List(跳跃列表)（其它还有 LevelDB 等也使用了跳跃列表）。

RBT 红黑树与 Skip List(跳跃列表)简单对比：

RBT 红黑树

插入、查询时间复杂度 O(logn)
数据天然有序
实现复杂，设计变色、左旋右旋平衡等操作
需要加锁

Skip List 跳跃列表

插入、查询时间复杂度 O(logn)
数据天然有序
实现简单，链表结构
无需加锁

二、Skip List 算法分析

2.1 Skip List 论文

这里贴出 Skip List 的论文，需要详细研究的请看论文，下文部分公式、代码、图片出自该论文。

Skip Lists: A Probabilistic Alternative to Balanced Trees

https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf

2.2 Skip List 动态图

先通过一张动图来了解 Skip List 的插入节点元素的流程，此图来自维基百科。

2.3 Skip List 算法性能分析

2.3.1 计算随机层数算法

首先分析的是执行插入操作时计算随机数的过程，这个过程会涉及层数的计算，所以十分重要。对于节点他有如下特性：

节点都有第一层的指针
节点有第 i 层指针，那么第 i+1 层出现的概率为 p
节点有最大层数限制，MaxLevel

计算随机层数的伪代码：

论文中的示例

Java 版本

public int randomLevel(){    int level = 1;    // random()返回一个[0...1)的随机数    while (random() < p && level < MaxLevel){         level += 1;    }    return level;}

复制代码

代码中包含两个变量 P 和 MaxLevel，在 Redis 中这两个参数的值分别是：

p = 1/4MaxLevel = 64

复制代码

2.3.2 节点包含的平均指针数目

Skip List 属于空间换时间的数据结构，这里的空间指的就是每个节点包含的指针数目，这一部分是额外的内内存开销，可以用来度量空间复杂度。random()是个随机数，因此产生越高的节点层数，概率越低（Redis 标准源码中的晋升率数据 1/4，相对来说 Skip List 的结构是比较扁平的，层高相对较低）。其定量分析如下：

level = 1 概率为 1-p
level >=2 概率为 p
level = 2 概率为 p(1-p)
level >= 3 概率为 p^2
level = 3 概率为 p^2(1-p)
level >=4 概率为 p^3
level = 4 概率为 p^3(1-p)
……

得出节点的平均层数（节点包含的平均指针数目）：

所以 Redis 中 p=1/4 计算的平均指针数目为 1.33

2.3.3 时间复杂度计算

以下推算来自论文内容

假设 p=1/2，在以 p=1/2 生成的 16 个元素的跳过列表中，我们可能碰巧具有 9 个元素，1 级 3 个元素，3 个元素 3 级元素和 1 个元素 14 级（这不太可能，但可能会发生）。我们该怎么处理这种情况？如果我们使用标准算法并在第 14 级开始我们的搜索，我们将会做很多无用的工作。那么我们应该从哪里开始搜索？此时我们假设 SkipList 中有 n 个元素，第 L 层级元素个数的期望是 1/p 个；每个元素出现在 L 层的概率是 p^(L-1), 那么第 L 层级元素个数的期望是 n * (p^L-1)；得到 1 / p =n * (p^L-1)

1 / p = n * (p^L-1)n = (1/p)^LL = log(1/p)^n

复制代码

所以我们应该选择 MaxLevel = log(1/p)^n

定义：MaxLevel = L(n) = log(1/p)^n

推算 Skip List 的时间复杂度，可以用逆向思维，从层数为 i 的节点 x 出发，返回起点的方式来回溯时间复杂度，节点 x 点存在两种情况：

节点 x 存在(i+1)层指针，那么向上爬一级，概率为 p，对应下图 situation c.
节点 x 不存在(i+1)层指针，那么向左爬一级，概率为 1-p，对应下图 situation b.

设 C(k) = 在无限列表中向上攀升 k 个 level 的搜索路径的预期成本（即长度）那么推演如下：

C(0)=0C(k)=(1-p)×(情况b的查找长度) + p×(情况c的查找长度)C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)C(k)=1/p+C(k-1)C(k)=k/p

复制代码

上面推演的结果可知，爬升 k 个 level 的预期长度为 k/p，爬升一个 level 的长度为 1/p。

由于 MaxLevel = L(n)， C(k) = k / p，因此期望值为：(L(n) – 1) / p；将 L(n) = log(1/p)^n 代入可得：(log(1/p)^n - 1) / p；将 p = 1 / 2 代入可得：2 * log2^n - 2，即 O(logn)的时间复杂度。

三、Skip List 特性及其实现

2.1 Skip List 特性

Skip List 跳跃列表通常具有如下这些特性

Skip List 包含多个层，每层称为一个 level，level 从 0 开始递增
Skip List 0 层，也就是最底层，应该包含所有的元素
每一个 level/层都是一个有序的列表
level 小的层包含 level 大的层的元素，也就是说元素 A 在 X 层出现，那么想 X>Z>=0 的 level/层都应该包含元素 A
每个节点元素由节点 key、节点 value 和指向当前节点所在 level 的指针数组组成

2.2 Skip List 查询

假设初始 Skip List 跳跃列表中已经存在这些元素，他们分布的结构如下所示：

此时查询节点 88，它的查询路线如下所示：

从 Skip List 跳跃列表最顶层 level3 开始，往后查询到 10 < 88 && 后续节点值为 null && 存在下层 level2
level2 10 往后遍历，27 < 88 && 后续节点值为 null && 存在下层 level1
level1 27 往后遍历，88 = 88，查询命中

2.3 Skip List 插入

Skip List 的初始结构与 2.3 中的初始结构一致，此时假设插入的新节点元素值为 90，插入路线如下所示：

查询插入位置，与 Skip List 查询方式一致，这里需要查询的是第一个比 90 大的节点位置，插入在这个节点的前面， 88 < 90 < 100
构造一个新的节点 Node(90)，为插入的节点 Node(90)计算一个随机 level，这里假设计算的是 1，这个 level 时随机计算的，可能时 1、2、3、4...均有可能，level 越大的可能越小，主要看随机因子 x ，层数的概率大致计算为 (1/x)^level ，如果 level 大于当前的最大 level3，需要新增 head 和 tail 节点
节点构造完毕后，需要将其插入列表中，插入十分简单步骤 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

2.4 Skip List 删除

删除的流程就是查询到节点，然后删除，重新将删除节点左右两边的节点以链表的形式组合起来即可，这里不再画图

四、手写实现一个简单 Skip List

实现一个 Skip List 比较简单，主要分为两个步骤：

定义 Skip List 的节点 Node，节点之间以链表的形式存储，因此节点持有相邻节点的指针，其中 prev 与 next 是同一 level 的前后节点的指针，down 与 up 是同一节点的多个 level 的上下节点的指针
定义 Skip List 的实现类，包含节点的插入、删除、查询，其中查询操作分为升序查询和降序查询（往后和往前查询），这里实现的 Skip List 默认节点之间的元素是升序链表

3.1 定义 Node 节点

Node 节点类主要包括如下重要属性：

score -> 节点的权重，这个与 Redis 中的 score 相同，用来节点元素的排序作用
value -> 节点存储的真实数据，只能存储 String 类型的数据
prev -> 当前节点的前驱节点，同一 level
next -> 当前节点的后继节点，同一 level
down -> 当前节点的下层节点，同一节点的不同 level
up -> 当前节点的上层节点，同一节点的不同 level

package com.liziba.skiplist;
/** * <p> *      跳表节点元素 * </p> * * @Author: Liziba * @Date: 2021/7/5 21:01 */public class Node {
    /** 节点的分数值，根据分数值来排序 */    public Double score;    /** 节点存储的真实数据 */    public String value;    /** 当前节点的 前、后、下、上节点的引用 */    public Node prev, next, down, up;
    public Node(Double score) {        this.score = score;        prev = next = down = up = null;    }
    public Node(Double score, String value) {        this.score = score;        this.value = value;    }}

复制代码

3.2 SkipList 节点元素的操作类

SkipList 主要包括如下重要属性：

head -> SkipList 中的头节点的最上层头节点（level 最大的层的头节点），这个节点不存储元素，是为了构建列表和查询时做查询起始位置的，具体的结构请看 2.3 中的结构
tail -> SkipList 中的尾节点的最上层尾节点（level 最大的层的尾节点），这个节点也不存储元素，是查询某一个 level 的终止标志
level -> 总层数
size -> Skip List 中节点元素的个数
random -> 用于随机计算节点 level，如果 random.nextDouble() < 1/2 则需要增加当前节点的 level，如果当前节点增加的 level 超过了总的 level 则需要增加 head 和 tail(总 level)

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;        }    }

}一、简介

复制代码

跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

RBT 红黑树与 Skip List(跳跃列表)简单对比： RBT 红黑树

插入、查询时间复杂度 O(logn)
数据天然有序
实现复杂，设计变色、左旋右旋平衡等操作
需要加锁

Skip List 跳跃列表

插入、查询时间复杂度 O(logn)
数据天然有序
实现简单，链表结构
无需加锁

二、Skip List 算法分析

2.1 Skip List 论文

这里贴出 Skip List 的论文，需要详细研究的请看论文，下文部分公式、代码、图片出自该论文。 _Skip Lists: A Probabilistic Alternative to Balanced Trees _

https://www.cl.cam.ac.uk/teaching/2005/Algorithms/skiplists.pdf

2.2 Skip List 动态图

先通过一张动图来了解 Skip List 的插入节点元素的流程，此图来自维基百科。

2.3 Skip List 算法性能分析

2.3.1 计算随机层数算法

首先分析的是执行插入操作时计算随机数的过程，这个过程会涉及层数的计算，所以十分重要。对于节点他有如下特性：

节点都有第一层的指针
节点有第 i 层指针，那么第 i+1 层出现的概率为 p
节点有最大层数限制，MaxLevel

计算随机层数的伪代码： 论文中的示例 Java 版本

public int randomLevel(){    int level = 1;    // random()返回一个[0...1)的随机数    while (random() < p && level < MaxLevel){         level += 1;    }    return level;}

复制代码

代码中包含两个变量 P 和 MaxLevel，在 Redis 中这两个参数的值分别是：

p = 1/4MaxLevel = 64

复制代码

2.3.2 节点包含的平均指针数目

level = 1 概率为 1-p
level >=2 概率为 p
level = 2 概率为 p(1-p)
level >= 3 概率为 p^2
level = 3 概率为 p^2(1-p)
level >=4 概率为 p^3
level = 4 概率为 p^3(1-p)
……

得出节点的平均层数（节点包含的平均指针数目）：所以 Redis 中 p=1/4 计算的平均指针数目为 1.33

2.3.3 时间复杂度计算

以下推算来自论文内容假设 p=1/2，在以 p=1/2 生成的 16 个元素的跳过列表中，我们可能碰巧具有 9 个元素，1 级 3 个元素，3 个元素 3 级元素和 1 个元素 14 级（这不太可能，但可能会发生）。我们该怎么处理这种情况？如果我们使用标准算法并在第 14 级开始我们的搜索，我们将会做很多无用的工作。那么我们应该从哪里开始搜索？此时我们假设 SkipList 中有 n 个元素，第 L 层级元素个数的期望是 1/p 个；每个元素出现在 L 层的概率是 p^(L-1), 那么第 L 层级元素个数的期望是 n * (p^L-1)；得到 1 / p =n * (p^L-1)

1 / p = n * (p^L-1)n = (1/p)^LL = log(1/p)^n

复制代码

所以我们应该选择 MaxLevel = log(1/p)^n 定义：MaxLevel = L(n) = log(1/p)^n

推算 Skip List 的时间复杂度，可以用逆向思维，从层数为 i 的节点 x 出发，返回起点的方式来回溯时间复杂度，节点 x 点存在两种情况：

节点 x 存在(i+1)层指针，那么向上爬一级，概率为 p，对应下图 situation c.
节点 x 不存在(i+1)层指针，那么向左爬一级，概率为 1-p，对应下图 situation b.

设 C(k) = 在无限列表中向上攀升 k 个 level 的搜索路径的预期成本（即长度）那么推演如下：

C(0)=0C(k)=(1-p)×(情况b的查找长度) + p×(情况c的查找长度)C(k)=(1-p)(C(k)+1) + p(C(k-1)+1)C(k)=1/p+C(k-1)C(k)=k/p

复制代码

上面推演的结果可知，爬升 k 个 level 的预期长度为 k/p，爬升一个 level 的长度为 1/p。

三、Skip List 特性及其实现

2.1 Skip List 特性

Skip List 跳跃列表通常具有如下这些特性

Skip List 包含多个层，每层称为一个 level，level 从 0 开始递增
Skip List 0 层，也就是最底层，应该包含所有的元素
每一个 level/层都是一个有序的列表
level 小的层包含 level 大的层的元素，也就是说元素 A 在 X 层出现，那么想 X>Z>=0 的 level/层都应该包含元素 A
每个节点元素由节点 key、节点 value 和指向当前节点所在 level 的指针数组组成

2.2 Skip List 查询

假设初始 Skip List 跳跃列表中已经存在这些元素，他们分布的结构如下所示：此时查询节点 88，它的查询路线如下所示：

从 Skip List 跳跃列表最顶层 level3 开始，往后查询到 10 < 88 && 后续节点值为 null && 存在下层 level2
level2 10 往后遍历，27 < 88 && 后续节点值为 null && 存在下层 level1
level1 27 往后遍历，88 = 88，查询命中

2.3 Skip List 插入

Skip List 的初始结构与 2.3 中的初始结构一致，此时假设插入的新节点元素值为 90，插入路线如下所示：

查询插入位置，与 Skip List 查询方式一致，这里需要查询的是第一个比 90 大的节点位置，插入在这个节点的前面， 88 < 90 < 100
构造一个新的节点 Node(90)，为插入的节点 Node(90)计算一个随机 level，这里假设计算的是 1，这个 level 时随机计算的，可能时 1、2、3、4...均有可能，level 越大的可能越小，主要看随机因子 x ，层数的概率大致计算为 (1/x)^level ，如果 level 大于当前的最大 level3，需要新增 head 和 tail 节点
节点构造完毕后，需要将其插入列表中，插入十分简单步骤 -> Node(88).next = Node(90); Node(90).prev = Node(80); Node(90).next = Node(100); Node(100).prev = Node(90);

2.4 Skip List 删除

删除的流程就是查询到节点，然后删除，重新将删除节点左右两边的节点以链表的形式组合起来即可，这里不再画图

四、手写实现一个简单 Skip List

实现一个 Skip List 比较简单，主要分为两个步骤：

定义 Skip List 的节点 Node，节点之间以链表的形式存储，因此节点持有相邻节点的指针，其中 prev 与 next 是同一 level 的前后节点的指针，down 与 up 是同一节点的多个 level 的上下节点的指针
定义 Skip List 的实现类，包含节点的插入、删除、查询，其中查询操作分为升序查询和降序查询（往后和往前查询），这里实现的 Skip List 默认节点之间的元素是升序链表 ####

3.1 定义 Node 节点

Node 节点类主要包括如下重要属性：

score -> 节点的权重，这个与 Redis 中的 score 相同，用来节点元素的排序作用
value -> 节点存储的真实数据，只能存储 String 类型的数据
prev -> 当前节点的前驱节点，同一 level
next -> 当前节点的后继节点，同一 level
down -> 当前节点的下层节点，同一节点的不同 level
up -> 当前节点的上层节点，同一节点的不同 level

package com.liziba.skiplist;/** * <p> *      跳表节点元素 * </p> * * @Author: Liziba * @Date: 2021/7/5 21:01 */public class Node {    /** 节点的分数值，根据分数值来排序 */    public Double score;    /** 节点存储的真实数据 */    public String value;    /** 当前节点的 前、后、下、上节点的引用 */    public Node prev, next, down, up;    public Node(Double score) {        this.score = score;        prev = next = down = up = null;    }    public Node(Double score, String value) {        this.score = score;        this.value = value;    }}

复制代码

3.2 SkipList 节点元素的操作类

SkipList 主要包括如下重要属性：

head -> SkipList 中的头节点的最上层头节点（level 最大的层的头节点），这个节点不存储元素，是为了构建列表和查询时做查询起始位置的，具体的结构请看 2.3 中的结构
tail -> SkipList 中的尾节点的最上层尾节点（level 最大的层的尾节点），这个节点也不存储元素，是查询某一个 level 的终止标志
level -> 总层数
size -> Skip List 中节点元素的个数
random -> 用于随机计算节点 level，如果 random.nextDouble() < 1/2 则需要增加当前节点的 level，如果当前节点增加的 level 超过了总的 level 则需要增加 head 和 tail(总 level)

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;        }    }}

复制代码

发布于: 2021 年 11 月 27 日阅读数: 8

原文链接:【http://xie.infoq.cn/article/39a989fad26181a1cd1552a0b】。

李子捌

关注

华为云享专家 2020.07.20 加入

公众号【李子捌】

发布

暂无评论

创作场景

Skip List(跳跃列表) 它到底好在哪？今天我们不仅只聊为什么，还手写一个玩玩

一、简介

二、Skip List 算法分析

2.1 Skip List 论文

2.2 Skip List 动态图

2.3 Skip List 算法性能分析

2.3.1 计算随机层数算法

2.3.2 节点包含的平均指针数目

2.3.3 时间复杂度计算

三、Skip List 特性及其实现

2.1 Skip List 特性

2.2 Skip List 查询

2.3 Skip List 插入

2.4 Skip List 删除

四、手写实现一个简单 Skip List

3.1 定义 Node 节点

3.2 SkipList 节点元素的操作类

二、Skip List 算法分析

2.1 Skip List 论文

2.2 Skip List 动态图

2.3 Skip List 算法性能分析

2.3.1 计算随机层数算法

2.3.2 节点包含的平均指针数目

2.3.3 时间复杂度计算

三、Skip List 特性及其实现

2.1 Skip List 特性

2.2 Skip List 查询

2.3 Skip List 插入

2.4 Skip List 删除

四、手写实现一个简单 Skip List

3.1 定义 Node 节点

3.2 SkipList 节点元素的操作类

李子捌

评论