数据结构与算法——跳表

简介: 前面说到了二分查找,并且它是基于顺序表结构的,即数组,如果直接用于链表,时间复杂度会比较的高,是 O(logn),一般我们不会这样做。那么有没有基于链表的二分查找呢?答案就是今天说到的跳跃链表。

1. 概述


前面说到了二分查找,并且它是基于顺序表结构的,即数组,如果直接用于链表,时间复杂度会比较的高,是 O(logn),一般我们不会这样做。那么有没有基于链表的二分查找呢?答案就是今天说到的跳跃链表。


2. 跳表长什么样子?


对于一般的链表,我们进行查找的话,需要遍历整个链表,就像下面这样:如果我们要找节点 9 ,需要遍历 9 个节点。

如果我们在原始链表之上建立一级链表,会是什么样子呢?如下图:

新建立的一级链表,我们叫做索引层或是索引,那么建立了一级索引之后,再来查找节点 9,会遍历多少节点呢?我们从第一级索引中开始查找,到了节点 9 的时候,通过向下的指针,可以找到节点 9,总共遍历了 6 个节点,相比没有索引,查找的效率提高了。

这样效果其实还不是非常的明显,如果我们再加上几级索引,查找会不会更快呢?

如上图,总共建立了三级索引,现在查找节点 9 ,只需要遍历 5 个节点了,查找的效率再一步提升了。其实,上面我举的例子,总共只有 10 个节点,所以看不出来性能有多大的提升,但是在实际的开发中,存储的数据成千上万,那么跳表的效率就更能体现了。


3. 跳表分析


通过上面的理解,你应该知道了跳表,其实就是通过建立多级索引来提升查找效率的一种数据结构。跳表的查询时间复杂度是 O(logn),跟二分查找一样,空间复杂度是 O(n),因为每一级建立的索引的节点个数都是上一级的一半,总共加起来就还需要原始链表的空间大小。

综合分析,其实你已经不能看到,跳表其实利用的是空间换时间的思想。

其实跳表不只是能够在 O(logn) 内查询数据,并且也可以高效的插入和删除数据,时间复杂度还是 O(logn)。

删除操作其实很简单,找到之后直接删除节点即可。

插入操作也类似,因为整个链表是有序的,所以查找之后,直接插入。只不过这里涉及到一个动态更新的问题。一般的动态数据结构都会维持平衡,保证插入查询操作的性能不会下降。

例如跳表,假如没有动态更新,则可能会出现插入之后,链表节点特别集中的问题:

在极端的情况下,跳表还是会退化为链表。

所以跳表借助了随机函数这种方式来维持整个索引的平衡性,每插入一个节点,都会生成一个随机函数 k,然后不仅是在原始链表中插入这个节点,还会在 1-k 层索引中插入这个节点。


4. 跳表实现


跳表的具体实现其实还是比较复杂的,代码理解起来比较的困难,这里我就不贴出来了,大家有兴趣的可以到我的 Github 上面参考借鉴。点击进入我的 Github

只不过我们也不用死扣跳表的代码实现,在实际的开发环境中,我们能够利用已有的实现就很不错了,这就是避免重复造轮子。例如在 Java 中已经有跳表的两个实现类,分别是 ConcurrentSkipListSetConcurrentSkipListMap,并且是线程安全的。

相关文章
|
1月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
7月前
|
存储 NoSQL 算法
【高阶数据结构】跳表 -- 详解
【高阶数据结构】跳表 -- 详解
|
7月前
|
C语言 索引
嵌入式中一文搞定C语言数据结构--跳表
嵌入式中一文搞定C语言数据结构--跳表
47 0
|
7月前
|
NoSQL 算法 Java
数据结构之跳表理解
数据结构之跳表理解
98 0
|
7月前
|
NoSQL 算法 Java
数据结构之跳表理解
数据结构之跳表理解
49 0
数据结构之跳表理解
|
7月前
|
NoSQL Go Redis
golang数据结构篇之跳表
golang数据结构篇之跳表
53 0
|
7月前
|
存储 NoSQL Redis
Redis数据结构之——跳表skiplist
Redis数据结构之——跳表skiplist
|
存储 NoSQL Redis
Redis从入门到精通之底层数据结构跳表 SkipList
跳表(Skip List)是一种基于链表的数据结构,用于快速地插入、删除和查找元素。跳表通过多层级的指针数组来实现快速的操作,时间复杂度为O(log n),其中n为跳表中元素的个数。Redis中的有序集合(Sorted Set)就是通过跳表来实现的。
841 10
Redis从入门到精通之底层数据结构跳表 SkipList
|
存储 机器学习/深度学习 算法
数据结构之数组、链表、跳表——算法与数据结构入门笔记(三)
数据结构之数组、链表、跳表——算法与数据结构入门笔记(三)
|
存储 NoSQL 算法
【高阶数据结构】跳表
跳表的原理及其模拟实现