adlist.h/adlist.c
一、 adlist 的定义
由于 C 语言没有内置的链表这种常用的数据结构，因此 Redis 实现了自己的链表实现。
Redis 对链表的实现，包括链表（ list ）、链表节点（ listNode ）以及链表迭代器（ listIter ）三个数据结构。
其中，链表节点在 adlist.h/listNode 中进行了定义：
//链表节点
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
多个链表节点通过 prve 和 next 指针组成双端链表，如下图所示：
由多个链表节点组成的双端链表
在链表节点组成双端链表后，由链表（ adlist.h/list ）来持有双端链表的话，操作起来会更加方便。
链表在 adlist.h/list 中进行了定义：
//链表
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;
下图是一个 list 结构与三个 listNode 结构组成的链表：
由 list 结构与 listNode 结构组成的链表
迭代器在 adlist.h/listIter 中进行了定义：
//迭代器
typedef struct listIter {
// 当前迭代到的节点
listNode *next;
// 迭代的方向
// 0 表示从表头向表尾进行迭代
// 1 表示从表尾向表头进行迭代
int direction;
} listIter;
//迭代器进行迭代的方向
// 从表头向表尾进行迭代
#define AL_START_HEAD 0
// 从表尾到表头进行迭代
#define AL_START_TAIL 1
二、 adlist 的 API
adlist 的函数实现分为两种，一种是通过宏定义的函数，一种是普通函数。
- 宏定义函数
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
| listLength | 返回给定链表的长度，即所包含的节点个数 | O(1) |
| listFirst | 返回给定链表的表头节点 | O(1) |
| listLast | 返回给定链表的表尾节点 | O(1) |
| listPrevNode | 返回给定链表节点的前一个结点 | O(1) |
| listNextNode | 返回给定链表节点的后一个结点 | O(1) |
| listNodeValue | 返回给定链表节点的值 | O(1) |
| listSetDupMethod | 将给定的函数设置为给定链表的节点值复制函数 | O(1) |
| listSetFreeMethod | 将给定的函数设置为给定链表的节点值释放函数 | O(1) |
| listSetMatchMethod | 将给定的函数设置为给定链表的节点值对比函数 | O(1) |
| listGetDupMethod | 返回给定链表当前正在使用的节点值复制函数 | O(1) |
| listGetFree | 返回给定链表当前正在使用的节点值释放函数 | O(1) |
| listGetMatchMethod | 返回给定链表当前正在使用的节点值对比函数 | O(1) |
- 普通函数
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
| listCreate | 创建一个不包含任何节点的空链表 | O(1) |
| listRelease | 释放给定链表，包括链表中的所有节点 | O(N)，N为链表中的节点数 |
| listAddNodeHead | 将包含给定值的新节点插入到给定链表的表头 | O(1) |
| listAddNodeTail | 将包含给定值的新节点插入到给定链表的表尾 | O(1) |
| listInsertNode | 将包含给定值的新节点插入到给定节点的之前或之后 | O(1) |
| listDelNode | 从给定链表中删除给定节点 | O(1) |
| listGetIterator | 为给定链表创建一个迭代器，并为其配置迭代方向 | O(1) |
| listNext | 返回迭代器当前所指向的链表节点 | O(1) |
| listReleaseIterator | 释放给定迭代器 | O(1) |
| listDup | 复制给定链表，并返回复制后的副本 | O(N)，N为链表中的节点数 |
| listSearchKey | 查找并返回链表中包含给定值的结点，查找方向为从头至尾 | O(N)，N为链表中的节点数 |
| listIndex | 查找并返回链表中在给定索引上的结点，索引值从零开始，可以为负（索引为负表示从表尾开始查找，-1 表示表尾节点，-2 表示倒数第二个结点） | O(N)，N为链表中的节点数 |
| listRewind | 将给定迭代器的方向设置为从头到尾（AL_START_HEAD），并将迭代指针重新指向表头节点 | O(1) |
| listRewindTail | 将给定迭代器的方向设置从尾到头（AL_START_TAIL），并将迭代指针重新指向表尾节点 | O(1) |
| listRotate | 将链表的表尾结点弹出，并插入到链表的表头，成为新的表头结点 | O(1) |
三、 adlist 的特性
双端链表
链表节点有 prev 和 next 指针，所以获取某节点的前后结点的复杂度都为O(1)。无环
链表无环，即链表的表头结点的 prev 指针和表尾节点的 next 指针都指向 NULL ，所以在通过迭代器对链表进行访问时（无论方向），都会以 NULL 为结尾，不会出现循环。带有表头结点和表尾结点
list 结构带有 head 和 tail 指针，所以获取某链表的头尾结点的复杂度都为O(1)。带有链表长度
list 结构带有 len 属性，所以获取某链表的长度的复杂度仅为O(1)。多态
链表节点使用 void * 指针来持有节点值，所以链表可以用于保存各种类型的值。
