跳跃链表 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> 接口。
1167 0
|
1天前
|
算法
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
LeetCode刷题---19. 删除链表的倒数第 N 个结点(双指针-快慢指针)
|
1天前
|
存储
LeetCode刷题---817. 链表组件(哈希表)
LeetCode刷题---817. 链表组件(哈希表)
|
1天前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
1天前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
|
1天前
|
算法 安全 数据处理
LeetCode刷题---707. 设计链表(双向链表-带头尾双结点)
LeetCode刷题---707. 设计链表(双向链表-带头尾双结点)
|
1天前
leetcode代码记录(移除链表元素
leetcode代码记录(移除链表元素
10 0
【每日一题】LeetCode——链表的中间结点
【每日一题】LeetCode——链表的中间结点
|
1天前
|
C++
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交
|
1天前
|
存储 算法
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)
LeetCode刷题--- 61. 旋转链表(快慢指针+闭合为环)