Redis(八)-Redis的list列表的数据结构-快速链表

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 数组时需要一块连续的内存空间来存储的,而链表值需要零散的内存碎片,数组的插入和删除的时间复杂度是0(n),查询的某个元素的时间复杂度是O(1)。

链表回顾

链表和数组

数组时需要一块连续的内存空间来存储的,而链表值需要零散的内存碎片,数组的插入和删除的时间复杂度是0(n),查询的某个元素的时间复杂度是O(1)。而链表插入和删除的时间复杂度是O(1),查询某个节点的时间复杂度是O(n)通过指针相连即可。如下图所示:

单链表

单链表是最简单的链表,链表中的每一个内存块称之为“结点”,每个结点Node包含两个部分,数据域data和后继指针next。单链表的第一个结点称为头结点,头结点记录了链表的基地址。其next指针指向下一个结点,通过头结点可以遍历整个链表,最后一个结点称为尾结点,尾结点的next指针指向空地址NULL。更多关于单链表的知识可以参考第八篇:链表的学习:链表的头插法和尾插法以及HashMap中链表结点的插入方式

双端链表

与单链表不同的是双向链表多了一个前驱指针prev。需要额外的空间存储前驱结点的地址,因此存储同样的数据,双端链表占用比单链表更多的空间,但是其优点是支持双向遍历。体现在如下两个方面:

1.在有序链表中查找某个元素,单链表由于只有后继指针,因此只能从前往后遍历查找时间复杂度为O(N)。双端链表可以双向遍历。

2.删除给定指针指向的结点,假设已经找到要删除的结点,要删除就必须知道其前驱节点和后继结点。单链表想要知道其前驱节点,就必须从头开始遍历。而双端链表由于保存了其前驱节点,因此时间复杂度是O(1)。

1b074f7594a9fccffeb6444e9f0f31bf_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

循环链表

循环链表与单链表和双链表的不同之处是其呈环装。单循环链表中其尾节点并非指向NULL而是指向头节点。双循环链表其头节点的前驱指针指向尾节点。尾节点的后继指针指向头节点。循环链表的优势在于链尾到链头,链头到链尾比较方便。适合处理具有环形结构的数据。

522dbd3963fa9179d15833a99a477d3a_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

Redis的链表

Redis链表使用的是双端无环链表。如下列表命令从左边添加元素:lpush lists 1 2 3。就是通过链表左边设置了三个元素。

11566f482259c5189fceea5782864b3e_2020072123313431.png

链表的结构

Redis使用一个listNode结构来表示链表的结点。

typedef struct listNode
  { 
    // 前置节点 
    struct listNode *prev; 
    // 后置节点 
    struct listNode *next; 
    // 节点的值 
    void *value; 
  } listNode;

用结构图表示就是:

ed87e19b3e11caf1119dd6be400c31f9_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

同时Redis为了方便操作链表,提供了一个list结构来持有链表

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *ptr,void *key);
  }list;

其中:

1.head记录了表头指针;

2.tail记录了表尾指针

3.len记录了链表长度,是链表长度计数器

dup、free和match成员则是用于实现多态链表所需的类型特定函数;

4.dup函数用于复制表节点所保存的值

5.free函数用于释放链表节点所保存的值

6.match函数则是用于对比链表节点所保存的值和另一个输入值是否相等。

下图就是由一个list结构和三个listNode结构组成的链表

af218e85beb475d1bf009495f136d09a_watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ1MzQ4MDg=,size_16,color_FFFFFF,t_70.png

链表的特性

1.双端:链表节点带有前驱、后继指针;获取某个节点的前驱、后继节点的时间复杂度是O(1)。

2.无环:链表为非循环链表表头节点和前驱指针和表尾的后继指针指向NULL,对链表的访问以NULL为终点。

3.带表头指针和表尾指针:通过list结构中的head和tail指针,获取表头和表尾节点的时间复杂度都是O(1)。

4.多态:链表节点使用void* 指针保存节点的值,并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用来保存不同的类型的值。

双端无环链表在Redis中的使用

链表在Redis中的应用非常广泛,列表对象的底层实现之一就是链表,此外如发布订阅、慢查询、监视器等功能也用到了链表,我们现在简单想一想为什么使用双端无环链表,而不是数组、单向链表等。既然列表对象的底层实现之一是链表,那么我们可以通过一个表格来分析一下列表对象的常用操作命令,如果分别使用数组、单链表和双端链表实现列表对象的时间复杂度对照如下:

操作\时间复杂度 数组 单链表 双端链表
rpush(从右边添加元素) O(1) O(1) O(1)
lpush(从左边添加元素) O(n) O(1) O(1)
lpop(从右边删除元素) O(1) O(1) O(1)
rpop(从左边删除元素) O(n) O(1) O(1)
lindex(获取指定索引下标的元素) O(1) O(n) O(n)
len(获取长度) O(n) O(n) O(1)
linsert(向某个元素前或后插入元素) O(n) O(n) O(1)
lrem(删除指定元素) O(n) O(n) O(n)
lset(修改指定索引下标元素) O(n) O(n) O(n)

但是双向链表因为使用两个额外的空间存储前驱和后继指针,因此在数据流较小的情况下会造成空间上的浪费(因为数据流小的时候速度上差别不大,但空间上差别很大)。这是一个时间换空间还是空间换时间的思想问题。Redis在列表对象中小数据量的时候使用压缩列表来作为底层实现,而大数据量的时候才会使用双向无环链表。

总结

本文首先对链表的相关知识点做了一个回顾,简单的介绍了单链表,双端链表,循环链表。接着就是着重介绍了Redis中的链表结构,Redis的链表采用的是双端无环链表。通过list结构来操作链表。


相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
1月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
2月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
55 8
|
2月前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
2月前
|
NoSQL 关系型数据库 MySQL
Redis 列表(List)
10月更文挑战第16天
26 2
|
2月前
|
消息中间件 存储 监控
redis 的List类型 实现 排行榜
【10月更文挑战第8天】
39 2
|
23天前
|
存储 NoSQL Java
Redis命令:列表模糊删除详解
通过本文的介绍,我们详细探讨了如何在Redis中实现列表的模糊删除。虽然Redis没有直接提供模糊删除命令,但可以通过组合使用 `LRANGE`和 `LREM`命令,并在客户端代码中进行模糊匹配,来实现这一功能。希望本文能帮助你在实际应用中更有效地操作Redis列表。
35 0
|
1月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
1月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
6月前
|
安全 Java
java线程之List集合并发安全问题及解决方案
java线程之List集合并发安全问题及解决方案
977 1
|
5月前
|
Java API Apache
怎么在在 Java 中对List进行分区
本文介绍了如何将列表拆分为给定大小的子列表。尽管标准Java集合API未直接支持此功能,但Guava和Apache Commons Collections提供了相关API。