关于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则是链表为实现特定性能的函数。

链表意识图：

链表的一些个性：

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

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