跳跃链表 skipList

简介: 二分查找的速度已经很快了,在此基础上的跳跃链表是一种以空间换时间的思想。 1.跳跃链表的思想 1.元素有序。2.有多层,层数越高,元素之间的间隔interval越大。 3.每个元素有一个指向下层该元素的指针,downPointer。 2.查找过程 1.从顶层开始,二分查找待查元素。定位到插入位置而找不到元素,则往下一层从待插入位置开始新的二分查找。2.不断重复上述过程,直至找到元
二分查找的速度已经很快了,在此基础上的 跳跃链表是一种以空间换时间的思想。


1.跳跃链表的思想

1.元素有序。

2.有多层,层数越高,元素之间的间隔interval越大。

3.每个元素有一个指向下层该元素的指针,downPointer。

2.查找过程

1.从顶层开始,二分查找待查元素。定位到插入位置而找不到元素,则往下一层从待插入位置开始新的二分查找。

2.不断重复上述过程,直至找到元素或在最底层查找结束。

3.配图

图3-1 大致说明了用法,但少了指向下层元素的指针。


图3-1 跳跃链表示意图


图3-2 跳跃链表示意图

目录
相关文章
java.util.concurrent.ConcurrentSkipListSet 基于跳跃链表的并发set
1.定义 public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {} 明显地,我们的元素需要实现 comparable<E> 接口。
1218 0
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
102 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
132 2
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
168 1
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
存储 SQL 算法
LeetCode 83题:删除排序链表中的重复元素【面试】
LeetCode 83题:删除排序链表中的重复元素【面试】