Redis 源码分析链表(list)

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis 源码分析链表(list)

list 简介



redis 的链表没有什么特别之处,就是普通的双向链表 adlist.c/listNode。


typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;


多个 listNode 可以通过 prev 和 next 组成双端链表,如下所示:


image.png


说明:头节点和尾节点的 prev, next 分别指向 null。


可以通过 listNode 结构来组成链表,但使用 adlist.c/list 来持有链表会更加方便:


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


一个 list 结构和三个 listNode 结构的链表


image.png


链表特征


  • 双端:链表节点带有 prev 和 next 指针, 获取某个节点的前置节点和后置节点的复杂度都是 O(1).


  • 无环:头节点的 prev 指针和表尾 next 指针都指向 null, 对链表的访问 null 为终点。


  • 带表头指针和表尾指针:通过 list 结构的 head 指针和 tail 指针,程序获取链表的表头节点和表尾节点的复杂度为 O(1).


  • 带链表长度计数器:程序使用 list 结构的 len 属性来对 list 持有的链表节点说开那个进行计数,程序获取链表中节点数量的负载度为 O(1).


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


迭代器



这里链表的迭代和数据是分配开的,采用的是类似迭代器模式,这个思想就是很多场景用到的 leveldb 中,大家可以搜索一下迭代器模式。


typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
listIter *listGetIterator(list *list, int direction)
{
    listIter *iter;
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    if (direction == AL_START_HEAD)
        iter->next = list->head;
    else
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}


运用场景


  • 链表广泛用韵用实现 Redis 的各种功能,比如列表键、发布订阅、满查询、监视器等。


  • 通过为链表设置不同的类型特定函数,Redis 链表可以用于保存各种不同类型的值。


参考资料




  • 《Redis 设计与实现》黄健宏


相关实践学习
基于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
相关文章
|
21天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
29天前
|
NoSQL 关系型数据库 MySQL
Redis 列表(List)
10月更文挑战第16天
17 2
|
1月前
|
消息中间件 存储 监控
redis 的List类型 实现 排行榜
【10月更文挑战第8天】
37 2
|
2月前
|
消息中间件 存储 NoSQL
剖析 Redis List 消息队列的三种消费线程模型
Redis 列表(List)是一种简单的字符串列表,它的底层实现是一个双向链表。 生产环境,很多公司都将 Redis 列表应用于轻量级消息队列 。这篇文章,我们聊聊如何使用 List 命令实现消息队列的功能以及剖析消费者线程模型 。
98 20
剖析 Redis List 消息队列的三种消费线程模型
|
1月前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
27 3
|
2月前
|
消息中间件 存储 NoSQL
4)深度解密 Redis 的列表(List)
4)深度解密 Redis 的列表(List)
32 1
|
2月前
|
存储 JSON NoSQL
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
这篇文章是关于Redis基本数据结构的学习笔记,包括了String、Hash、Set、List和SortedSet的介绍和常用命令。文章解释了每种数据结构的特点和使用场景,并通过命令示例演示了如何在Redis中操作这些数据结构。此外,还提供了一些练习示例,帮助读者更好地理解和应用这些数据结构。
redis基本数据结构(String,Hash,Set,List,SortedSet)【学习笔记】
|
5月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
5月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
5月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
53 2