list 简介
redis 的链表没有什么特别之处,就是普通的双向链表 adlist.c/listNode。
typedef struct listNode { struct listNode *prev; struct listNode *next; void *value; } listNode;
多个 listNode 可以通过 prev 和 next 组成双端链表,如下所示:
说明:头节点和尾节点的 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 结构的链表
链表特征
- 双端:链表节点带有 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 设计与实现》黄健宏