专栏首页sunsky跳跃表原理和实现

跳跃表原理和实现

跳跃表原理和实现

前提

有时候会被问到链表如果做到二分搜索,可能会有部分的人会去把链表中的值保存到数组来进行二分,但是如果知道跳跃表的话,那么这个数据结构就可以解决这个困惑,它允许快速查询一个有序连续元素的数据链表,它的效率可以做到和二分相同,都是O(logn)的平均时间复杂度,其空间复杂度为O(n)。

跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。----by 发明者像是redis中有序集合就使用到了跳跃表。

原理

性质

首先,应该要了解跳跃表的性质;

  1. 由很多层结构组成;
  2. 每一层都是一个有序的链表,排列顺序为由高层到底层,都至少包含两个链表节点,分别是前面的head节点和后面的nil节点;
  3. 最底层的链表包含了所有的元素;
  4. 如果一个元素出现在某一层的链表中,那么在该层之下的链表也全都会出现(上一层的元素是当前层的元素的子集);
  5. 链表中的每个节点都包含两个指针,一个指向同一层的下一个链表节点,另一个指向下一层的同一个链表节点;

可以看到,这里一共有4层,最上面就是最高层(Level 3),最下面的层就是最底层(Level 0),然后每一列中的链表节点中的值都是相同的,用指针来连接着。跳跃表的层数跟结构中最高节点的高度相同。理想情况下,跳跃表结构中第一层中存在所有的节点,第二层只有一半的节点,而且是均匀间隔,第三层则存在1/4的节点,并且是均匀间隔的,以此类推,这样理想的层数就是logN。

搜索

其基本原理就是从最高层的链表节点开始,如果比当前节点要大和比当前层的下一个节点要小,那么则往下找,也就是和当前层的下一层的节点的下一个节点进行比较,以此类推,一直找到最底层的最后一个节点,如果找到则返回,反之则返回空。

代码实现大致为:

find(x)   
{  
    p = top;  
    while (1) {  
        while (p->next->key < x)  
            p = p->next;  
        if (p->down == NULL)   
            return p->next;  
        p = p->down;  
    }  
}  

插入

既然要插入,首先需要确定插入的层数,这里有不一样的方法。1. 看到一些博客写的是抛硬币,只要是正面就累加,直到遇见反面才停止,最后记录正面的次数并将其作为要添加新元素的层;2. 还有就是一些博客里面写的统计概率,先给定一个概率p,产生一个0到1之间的随机数,如果这个随机数小于p,则将高度加1,直到产生的随机数大于概率p才停止,根据给出的结论,当概率为1/2或者是1/4的时候,整体的性能会比较好(其实当p为1/2的时候,也就是抛硬币的方法)。

当确定好要插入的层数以后,则需要将元素都插入到从最底层到第k层。

删除

在各个层中找到包含指定值的节点,然后将节点从链表中删除即可,如果删除以后只剩下头尾两个节点,则删除这一层。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 你所不知道的TIME_WAIT和CLOSE_WAIT

    然后打开Google,输入关键词:too many timewait。一定能找到解决方案,而排在最前面或者被很多人到处转载的解决方案一定是:

    sunsky
  • 2017,科学使用strace神器(附代码,举栗子)

      我感到惊讶,都2017年了,几乎没有人知道他们可以使用strace的了解所有事情。它总是我拔出的第一个调试工具之一,因为它通常在我运行的Linux系统上可用...

    sunsky
  • MQ选型之RabbitMQ

    MQ 是什么?队列是什么,MQ 我们可以理解为消息队列(message queue),队列我们可以理解为管道。以管道的方式做消息传递。        

    sunsky
  • 一起学Rust-实战leetcode(四)

    给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储一位数字。

    江湖安得便相忘
  • Redis系列(二)底层数据结构之双端链表

    Redis 已经是大家耳熟能详的东西了,日常工作也都在使用,面试中也是高频的会涉及到,那么我们对它究竟了解有多深刻呢?

    呼延十
  • 如何实现LRU缓存淘汰算法

    LRU:Least recently used,最近最少使用。缓存算法根据数据最近被访问的情况来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问...

    s_在路上
  • Go实现双向链表 | Redis 队列的实现

    本文介绍什么是链表,常见的链表有哪些,然后介绍链表这种数据结构会在哪些地方可以用到,以及 Redis 队列是底层的实现,通过一个小实例来演示 Redis 队列有...

    link1st
  • LeetCode 2 Add Two Numbers——用链表模拟加法

    给定两个非空的链表,代表两个非负整数。这两个整数都是倒叙存储,要求返回一个链表,表示这两个整数的和。

    TechFlow-承志
  • 图解 LeetCode 链表: 2. Add Two Numbers

    今天是 LeetCode 算法的 第 1 阶段第 4 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。

    用户2932962
  • [随缘一题]合并两个排序链表

    那么其实可以比较两个链表当前节点的值,哪个值小,就把它连接在新链表的后面,并将这个链表的当前指针后移一位.知道某一个链表为空,将另一个链表的所有值链接在后面即可...

    呼延十

扫码关注云+社区

领取腾讯云代金券