数据结构-跳表

一、定义

特点：

1、有多层链表，每层都是排序好的

2、每一个级别都是其更低级别的子集

3、除最底层Level0，每层每个索引节点包含两个指针，一个向下，一个向右；

如下：

二、复杂度

增删查可以在O(logn)时间内完成

数组可以二分，跳表就是实现可以二分的链表，

查询时从最上层开始，只要右侧节点小于所查节点就可以直接跳跃中间多个节点，故名“跳表”

相比平衡二叉树如红黑树，跳表最低一层包含全部节点且有序，可以按区间查找元素

如redis使用跳表 而非 红黑树

三、ConcurrentSkipListMap

Java集合框架ConcurrentSkipListMap就是使用skipList(跳表) 实现

数据结构-跳表

原文：https://www.cnblogs.com/yangfei629/p/13090016.html