其中 -1 表示 INT_MIN， 链表的最小值，1 表示 INT_MAX，链表的最大值。

1.跳表的特性

• 有多层结构，每一层都是一个有序的链表
• 最底层(Level 1)的链表包含所有元素
• 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
• 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

2.查找跳表

比如查找元素 117

• 比较 21,比 21 大,往后面找
• 比较 37,比 37大，比链表最大值小,从 37 的下面一层开始找
• 比较 71,比 71大,比链表最大值小,从 71 的下面一层开始找
• 比较 85,比 85大,从后面找
• 比较 117,等于117,找到了节点

3.增加跳表元素

4.删除元素

5.算法复杂度

• 空间复杂度

每一层的期望值：第一层n，第二层n/2，第三层n/2²，...，直到 n/2ⁿ=1。所以，总空间需求：

S = n + n/2 + n/2<sup>2</sup> + ... + n/2<sup>n</sup> < n(1 + 1/2 + 1/2<sup>2</sup> + ... + 1/2∞) =2n

因此他的空间复杂度= 2n = O(n)

• 时间复杂度 要求时间复杂度，先求一下跳表的期望高度，因为跳表的高度代表了一个元素查找时走过的最长路径。假设每个元素向上增长的概率为1/2，n个元素的期望高度为m，那么一个元素能增长到m层的概率为1/2^m，n个元素如果有一个能增长到m层就必然有n/2^m=1，所以求得m=log₂n,即时间复杂度=O(logn)

二、ConcurrentSkipListMap

在redis中和java中都有跳表的运用，redis的ListOperations和java的ConcurrentSkipListMap以及ConcurrentSkipListSet都是运用的跳表