Open Linkerist opened 5 years ago
链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度。
作为一种常用数据结构, 链表内置在很多高级的编程语言里面, 因为 Redis 使用的 C 语言并没有内置这种数据结构, 所以 Redis 构建了自己的链表实现。
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现。
举个例子, 以下展示的 integers 列表键包含了从 1 到 1024 共一千零二十四个整数:
redis> LLEN integers (integer) 1024 redis> LRANGE integers 0 10 1) "1" 2) "2" 3) "3" 4) "4" 5) "5" 6) "6" 7) "7" 8) "8" 9) "9" 10) "10" 11) "11"
integers 列表键的底层实现就是一个链表, 链表中的每个节点都保存了一个整数值。
integers
除了链表键之外, 发布与订阅、慢查询、监视器等功能也用到了链表, Redis 服务器本身还使用链表来保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer), 本书后续的章节将陆续对这些链表应用进行介绍。
本章接下来的内容将对 Redis 的链表实现进行介绍, 并列出相应的链表和链表节点 API 。
因为已经有很多优秀的算法书籍对链表的基本定义和相关算法进行了详细的讲解, 所以本章不会介绍这些内容, 如果不具备关于链表的基本知识的话, 可以参考《算法:C 语言实现(第 1 ~ 4 部分)》一书的 3.3 至 3.5 节, 或者《数据结构与算法分析:C 语言描述》一书的 3.2 节, 又或者《算法导论(第三版)》一书的 10.2 节。
每个链表节点使用一个 adlist.h/listNode 结构来表示:
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
多个 listNode 可以通过 prev 和 next 指针组成双端链表, 如图 3-1 所示。 虽然仅仅使用多个 listNode 结构就可以组成链表, 但使用 adlist.h/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;
list 结构为链表提供了表头指针 head 、表尾指针 tail , 以及链表长度计数器 len , 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数:
图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表: Redis 的链表实现的特性可以总结如下:
表 3-1 列出了所有用于操作链表和链表节点的 API 。
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com
链表
链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度。
作为一种常用数据结构, 链表内置在很多高级的编程语言里面, 因为 Redis 使用的 C 语言并没有内置这种数据结构, 所以 Redis 构建了自己的链表实现。
链表在 Redis 中的应用非常广泛, 比如列表键的底层实现之一就是链表: 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现。
举个例子, 以下展示的 integers 列表键包含了从 1 到 1024 共一千零二十四个整数:
integers
列表键的底层实现就是一个链表, 链表中的每个节点都保存了一个整数值。除了链表键之外, 发布与订阅、慢查询、监视器等功能也用到了链表, Redis 服务器本身还使用链表来保存多个客户端的状态信息, 以及使用链表来构建客户端输出缓冲区(output buffer), 本书后续的章节将陆续对这些链表应用进行介绍。
本章接下来的内容将对 Redis 的链表实现进行介绍, 并列出相应的链表和链表节点 API 。
因为已经有很多优秀的算法书籍对链表的基本定义和相关算法进行了详细的讲解, 所以本章不会介绍这些内容, 如果不具备关于链表的基本知识的话, 可以参考《算法:C 语言实现(第 1 ~ 4 部分)》一书的 3.3 至 3.5 节, 或者《数据结构与算法分析:C 语言描述》一书的 3.2 节, 又或者《算法导论(第三版)》一书的 10.2 节。
链表和链表节点的实现
每个链表节点使用一个 adlist.h/listNode 结构来表示:
多个 listNode 可以通过 prev 和 next 指针组成双端链表, 如图 3-1 所示。 虽然仅仅使用多个 listNode 结构就可以组成链表, 但使用 adlist.h/list 来持有链表的话, 操作起来会更方便:
list 结构为链表提供了表头指针 head 、表尾指针 tail , 以及链表长度计数器 len , 而 dup 、 free 和 match 成员则是用于实现多态链表所需的类型特定函数:
图 3-2 是由一个 list 结构和三个 listNode 结构组成的链表: Redis 的链表实现的特性可以总结如下:
链表和链表节点的 API
表 3-1 列出了所有用于操作链表和链表节点的 API 。
重点回顾
本文暂取自代码、网络或书籍,只用作学习备忘,不作盈利等他用,如有侵权,请联系Linkerist@163.com