redis链表

每个链表和链表节点的实现

链表节点结构

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 *prt, void *key);
} list;

dup、free、match成员用于实现多态链表所需的类型特定函数：

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

Redis的链表实现特性

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

API

• listSetDupMethod：将给定的函数设置为链表的节点复制函数，O(1)
• listGetDupMethod：返回链表正在使用的节点复制函数，O(1)
• listSetFreeMethod：将给定的函数设置成链表节点的释放函数，O(1)
• listGetFreeMethod：反馈链表正在使用的节点释放函数，O(1)
• listSetMatchMethod：将给定的函数设置成链表节点的对比函数，O(1)
• listGetMatchMethod：反馈链表正在使用的节点对比函数，O(1)
• listLength：返回链表长度，O(1)
• listFirst：返回链表头结点，O(1)
• listLast：返回链表尾节点，O(1)
• listPrevNode：返回前置节点，O(1)
• listNextNode：返回后置节点，O(1)
• listNodeValue：返回节点保存的值，O(1)
• listCreate：创建一个空链表，O(1)
• listAddNodeHead：添加节点到链表头，O(1)
• listAddNodeTail：添加节点到链表尾，O(1)
• listInsertNode：将新节点添加到给定节点之前或者之后，O(1)
• listSearchKey：反会链表中包含给定值的节点，O(N)
• listIndex：返回链表中给定索引的节点，O(N)
• listDelNode：删除给定节点，O(N)
• listRotate：弹出尾节点，并弹出，插入到表头，O(1)
• listDup：复制一个给链表，O(N)
• listRelease：释放给定链表以及链表中所有节点，O(N)

本文使用 文章同步助手 同步