关于redis:redis学习之二链表

之前相关联文章：redis 学习之一 SDS

链表数据结构

链表节点构造：

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

链表构造：

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;

链表提供了表头指针 head、表尾指针 tail，还有链表长度属性 len，dup/free/match 则是链表为实现特定性能的函数。

链表意识图：

链表的一些个性：

每个节点有指向前与后的节点指针，因而获取某节点的前后节点工夫复杂度为 O(1)。
表头的 prev 指针与表尾的 next 指针都指向 NULL。
有指向表头与表尾的指针，因而获取头尾节点时工夫复杂度为 O(1)。
链表有属性 len 记录链表长度，因而获取链表长度为 O(1)。

此文大部分内容都来自于黄健宏《Redis 设计与实现》一书