链表提供了高效的节点重排能力, 以及顺序性的节点访问方式, 并且可以通过增删节点来灵活地调整链表的长度.
列表键的底层实现之一就是链表. 当一个列表中包含了数量比较多的元素, 或者列表中元素都是比较长的字符串时, Redis 就会使用链表作为列表键的底层实现.
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;
dup,free 和 match 成员是用于实现多态链表所需的类型特定函数:
dup 函数用于复制链表节点所保存的值;
free 函数用于释放链表节点所保存的值;
match 函数用于对比链表节点所保存的值和另一个输入值是否相等.
Redis 链表
特性:
双端: 链表节点带有 prev 和 next 指针, 获取某个节点的前置节点和后置节点的复杂度都是 O(1).
无环: 表头结点的 prev 指针和表尾节点的 next 指针都指向 NULL, 对链表的访问以 NULL 为终点.
带表头指针和表尾指针: 通过 head 和 tail 指针, 程序获取链表表头表尾节点的复杂度为 O(1)
带链表长度计数器: len 做计数, 获取节点数量复杂度为 O(1)
多态: 链表节点用的是 void * 保存值, list 结构的 dup,free,match 三个属性为节点值设置类型特定函数, 所以链表可以用于保存各种不同类型的值.
3.2 链表和链表节点的 API
3.3 重点回顾
来源: http://www.jianshu.com/p/92e4c5be2f18