Redis(二):链表(Linked List)

Dear 丶 2022-05-25 12:53 206阅读 0赞

###### 链表 ######

链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。

作为一种常用的数据结构，链表内置在很多高级的编程语言里面，因为Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。

链表在Redis中应用非常广泛，比如列表建的底层实现之一就是链表，当一个列表包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis会使用链表作为列表键的底层实现。

举个例子，以下展示的integers列表键包含了从1到1024共一千零二十四个整数：

![20180515104320596][]

integers列表键的底层实现就是一个链表，链表中的每个节点都保存了一个整数值。

除了链表键之外，发布与订阅，慢查询，监视器等功能也都用到了链表，Redis服务器本身还使用链表来保存多个客户端的状态信息，以及使用链表来构建客户端输出缓冲区。

###### 链表和链表节点的实现 ######

每个链表节点使用一个adlist.h/listNode结构来表示：

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

多个listNode可以通过prev和next指针组成双端链表，如下图所示。

![20180515104903642][]

虽然仅仅使用多个listNode结构就可以组成链表了，但是这样对链表的操作效率不高。所以有了一个新的数据结构。adlist.h/list

typedef struct list{
       listNode *head;
       listNode *tail;
       unsigned long len;
       void *(*duo)(void *ptr);
       void *(*free)(void *ptr);
       int (*match)(void *ptr,void *key);
    }list;

list结构为链表提供了表头指针head、表尾指针tail，以及链表的长度计算器len,而dup、free和match成员则是用于实现动态链表所需的类型和特定函数：

*  dup函数用于复制链表所保存的值；
 *  free函数用于释放链表节点所保存的值；
 *  match函数则用于对比链表节点所保存的值和另外一个输入值是否相等。

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

![20180515105556934][]

Redis的链表实现的特征可以总结如下：

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

无环：表头节点prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点。

带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的时间复杂度是O(1)。

带链表长度计算器：程序使用list结构的len属性来对list持有的链表节点进行计数，程序获取链表中节点数量的时间复制读是O(1)。

多态：链表节点使用void\*指针来保存节点值，并且通过list结构的dup，free，match等三个属性为节点值设置类型特定函数，所以链表可以保存各种不同类型的值

[20180515104320596]: /images/20220525/97f0268e526a400f96a571bc2b508cf1.png
[20180515104903642]: /images/20220525/ef15b66f32af45718503e802fd8b91cf.png
[20180515105556934]: /images/20220525/1a1f53615251438ea2657835c8393cff.png

发表评论取消回复

表情：

评论列表（有 0 条评论，206人围观）

还没有评论，来说两句吧...

相关阅读

相关链表【Linked List】

1、链表介绍链表是有序的列表，但是它在内存中是存储如下： ![在这里插入图片描述][ba169e310af440f290db3aae8b855d0c.png]

古城微笑少年丶/ 2023年09月27日 08:29/ 0 赞/ 121 阅读

相关链表Linked List-链表删除 Deletion in Linked List（5）

1.从头中尾删除元素 You can delete an element in a list from: Beginning Middle End

Love The Way You Lie/ 2023年09月24日 19:24/ 0 赞/ 72 阅读

相关 Linked List 链表操作

系列文章目录 [Array 数组操作][Array] [Linked List 链表操作][Linked List] [Stack 栈操作][Stack] --

灰太狼/ 2022年10月21日 03:45/ 0 赞/ 195 阅读

相关数据结构：链表(linked-list)

在讨论链表(linked-list)之前，需要明确几个概念：线性表（顺序表, list, linear list）, 数组(array)，链表(linked-list)。线

今天药忘吃喽~/ 2022年08月22日 00:24/ 0 赞/ 252 阅读

相关排序链表（Sort linked list）

Sort List Sort a linked list in O(n log n) time using constant space complexity 分别使用快

刺骨的言语ヽ痛彻心扉/ 2022年08月12日 11:30/ 0 赞/ 18 阅读

相关 [Leetcode][python]Linked List Cycle/Linked List Cycle II/环形链表/环形链表 II

Linked List Cycle 题目大意判断一个链表中是否存在着一个环，能否在不申请额外空间的前提下完成？解题思路哈希表快慢指针代码

雨点打透心脏的1/2处/ 2022年06月04日 01:59/ 0 赞/ 198 阅读

相关链表(Linked-list)

链表(linked-list) 链表是线性表的链式存储方式，链表的内存是不连续的，链表通过一个指向下一个元素地址的引用将所有的元素串起来。 ![这里写图片描述][70

港控/mmm°/ 2022年05月27日 23:25/ 0 赞/ 231 阅读

相关 Redis(二):链表(Linked List)

链表链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。作为一种常用的数据结构，链表内置在很多高级的编程语言里面，因

Dear 丶/ 2022年05月25日 12:53/ 0 赞/ 207 阅读

相关 redis list ( 链表 )

list类型其实就是一个双向链表。通过push,pop操作从链表的头部或者尾部添加删除元素。这使得list既可以用作栈，也可以用作队列。上进上出是栈，特点：数据

拼搏现实的明天。/ 2022年05月10日 04:04/ 0 赞/ 209 阅读

相关 [LeetCode] Reverse Linked List II 倒置链表之二

本题是要对链表区间内的数据进行翻转，如下图所示。 ![20190420152335243.jpg][] 如果是数组，知道起始位置m和终止位置n的下标，即可通过中间变量根据下

叁歲伎倆/ 2022年04月24日 07:40/ 0 赞/ 108 阅读