Redis设计与实现笔记二

链表：

链表和链表节点的实现：

链表节点使用一个adlist.h/listNode结构表示：

typedef struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
}listNode;

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

使用adlist.h/list来持有链表。

typedef struct list{
    //表头节点
    listNode *head;
    //表尾节点
    listNode *tail;
    //链表所包含的节点数量
    unsigned long len;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void *(*free)(void *ptr);
    //节点值对比函数
    int (*match)(void *pre , void *key);
}list;

上图是一个由list结构和三个listNode结构组成的链表。

Redis链表实现特性:

1. 双端：链表节点带有prev和next指针，获取某个节点的前置和后置复杂度都是O(1)
2. 无环：表头节点的prev和表尾的next都指向NULL，对链表访问都以NULL为终点
3. 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点都是O(1)
4. 带链表长度计数器：获取链表中节点数量的复杂度为O(1)
5. 多态：链表节点使用void* 指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。