Redis数据结构(二) — 链表

た入场券 2022-02-16 00:49 250阅读 0赞

## 链表 ##

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

列表键的底层实现之一就是链表. 当一个列表键包含了数量比较多的元素, 又或者列表中包含的元素都是比较长的字符串时, Redis就会使用链表作为列表键的底层实现

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

#### 1.实现 ####

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

多个listNode可以通过prev和next指针组成双端链表

仅仅通过多个listNode结构就可以组成链表, 但是用adlist.h/list来持有链表的话,操作起来会更方便:

typedef struct list {
        
        listNode * head;
        listNode * tail;
        unsigned long len;
        //节点值复制函数
        void *(*dup)(void *ptr);
        //节点值释放函数
        void (*free)(void *pte);
        //节点值对比函数
        int (*match)(void *ptr, void *key);
    }list;

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

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

#### 2.特点 ####

*  双端 : 链表节点带有prev和next指针, 获取前置节点和后置节点的复杂度都是O(1)
 *  无环 : 表头节点的prev和表尾节点的next都指向NULL
 *  带表头指针和表尾指针 :
 *  带链表长度计数器
 *  多态 :使用void\*指针来保存节点值，并可以通过list结构的dup, free, match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值