Redis-链表

链表是一种基本的数据结构，它是由一系列的节点组成，每个节点上都包括有两部分数据：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。新增节点时，可以做到O(1)的复杂度。链表一般分为：单向链表、双向链表、循环链表。Redis 的链表，属于双向链表。

链表中节点结构体在文件 src/adlist.h 如下：

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

其中 prev 指向当前节点的上一个节点，next 指向当前节点的下一个节点；value 用来存储当前节点的数据，其中 prev 和 next 共同组成了链表的指针域，value 则是它的数据域，因为是 void *，所以可以在节点中存储任意的数据类型。

多个 listNode 通过 prev 和 next 就可以组成一个双向链表。但是 Redis 还是决定用一个结构体来管理链表。这是它的结构体：

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

head、tail 和 len 就不多做介绍了，dup、free 和 match 主要是实现多态链表的函数，因为 listNode 的 value 可以存储任意类型的数据，在复制、释放或者比较时，对于不同的类型，需要有不同的操作，所以，在生成链表时，需要对应的set每种类型的操作（复制、释放和对比）API。
在 src/adlist.h 64行开始，有6个宏定义的方法，作为 setter 和 getter。

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

对于链表结构，获取前一个节点和后一个节点的复杂度都是O(1)，因为有 len 属性，所以获取链表长度复杂度也是O(1)。在网上找了些文章，在 list 的实现，主要就用到了链表，其实可以想到，因为 list 本身就是一个链表的结构。

aslist.h 文件中还有一个结构体

typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

这个是 list 的迭代器，next 指针指向下个节点，direction 是定义迭代的方向，AL_START_HEAD 和 AL_START_TAIL 分别对应从头部 -> 尾部的方向、尾部 -> 头部的方向。相关的方法有：

listIter *listGetIterator(list *list, int direction)    // 初始化一个 链表迭代器

listNode *listNext(listIter *iter)  // 迭代器 next 方法

void listReleaseIterator(listIter *iter);   // 迭代器释放

void listRewind(list *list, listIter *li);  // 迭代器恢复指针至表头位置

void listRewindTail(list *list, listIter *li);  // 迭代器恢复指针至表尾位置