adlist作為Redis中的雙端鍊錶，在Redis中被廣泛的應用到了很多地方，比如slowlog的存儲，主從複製中報錯客戶端，list數據結構的實現等等，很多都與此相關，所以也是非常重要的一個資料結構。
一）、Redis中雙端鍊錶的資料結構
（建議：redis影片教學）
雙端鍊錶（以下程式碼定義在src/adlist.h）：
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;雙端鍊錶的節點（以下程式碼定義在src/adlist.h）：
typedef struct listNode {
struct listNode *prev; //当前节点的上一个节点
struct listNode *next; //当前节点的下一个节点
void *value; //当前节点存储的值，可以任意类型
} listNode;
list 透過head和tail兩個指標分別指向鍊錶的頭尾兩端，使得遍歷鍊錶可以從正反兩個順序進行遍歷，而listNode 的void *value，則可以保存任意數據，並可以通過dup，free，match來自定義如何處理listNode的值。
二、雙端鍊錶的簡單操作
建立鍊錶（以下程式碼定義在src/adlist.c）：
list *listCreate(void)
{
struct list *list; //初始化链表
//为链表分配内存
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
//为空链表设置初始值
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}追加到鍊錶結尾（以下程式碼定義在src/adlist.c）：
list *listAddNodeTail(list *list, void *value)
{
listNode *node; //初始化node节点
//为新的node节点分配内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
//为node节点设置值
node->value = value;
if (list->len == 0) {
//如果空链表则 将头尾指向 新节点 并后继前驱节点设置为NULL
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
//否则将节点的前驱节点设置为原来的尾部节点
node->prev = list->tail;
//由于追加到尾部，后继节点为NULL
node->next = NULL;
//之前的尾部节点的后继节点设置为新增的节点
list->tail->next = node;
//将列表的尾部节点指针指向新增的节点
list->tail = node;
}
//增加链表长度
list->len++;
return list;
}遍歷鍊錶：
常用的遍歷鍊錶有兩種方式，一個是根據鍊錶長度透過while循環去手動遍歷，還有一種是用Redis雙端鍊錶提供的迭代器來遍歷。
手動遍歷（以下程式碼定義在 src/adlist.c 中的 記憶體釋放函數）：
void listRelease(list *list)
{
unsigned long len;
//current表示当前遍历的游标指针，next表示下次遍历的游标指针（next作为临时变量用于保存下一个节点）
listNode *current, *next;
//将current指向头部节点
current = list->head;
//计算长度（其实就是 listLength(list)）
len = list->len;
//通过长度递减的方式进行遍历，便利到长度为0的时候，遍历结束
while(len--) {
//保存下次循环的节点指针
next = current->next;
//释放掉当前节点，如果设置释放节点的回调函数，则执行用户自定义的函数
if (list->free) list->free(current->value);
zfree(current);
//将游标指向下个节点
current = next;
}
zfree(list);
}迭代器方式遍歷請見下文。
三）、雙端鍊錶的迭代器
Redis 為了方便對鍊錶的迭代，對鍊錶進行了迭代器的封裝，迭代器結構如下（以下程式碼定義在src/adlist .h）：
typedef struct listIter {
listNode *next; //迭代器指向的下一个节点
//迭代方向，由于双端链表保存了head和tail的值，所以可以进行两个方向的迭代
//AL_START_HEAD表示从头向后遍历，AL_START_TAIL表示从尾部向前遍历
int direction;
} listIter;迭代器使用實例：
//l表示list结构，n表示listNode结构，listNode的值保存的是sds字符串
//创建迭代器对象
iter = listGetIterator(l, AL_START_HEAD);
//循环获取下一个需要遍历的节点
while ((n = listNext(iter))) {
//输出返回的节点n的value值
printf("Node Value: %s\n", listNodeValue(n));
}更多redis知識請關注redis入門教學欄位。
以上是Redis中的雙端鍊錶實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！
