Redis设计与实现第三章笔记
date
Jul 15, 2021
slug
Redis设计与实现第三章笔记
status
Published
tags
读书笔记
summary
链表
type
Post
C语言没有链表，所以Redis自己构建了链表
用在的地方：
链表实现的列表键，发布与订阅，慢查询，监视器，Redis服务器用于保存多个客户端的状态信息，构建客户端输出缓冲区。
3.1 链表与链表节点的实现
由list结构来持有链表：
举例：
Redis链表实现特性：
- 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
- 无环：表头节点的prev指针和表尾节点的next指针都指向null，对链表的访问以null为终点
- 带表头指针和表尾指针：获取表头和表尾的复杂度为O(1)
- 多态：链表节点使用void* 指针来保存节点值，并可以通过list的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值