Redis中的双端链表实现

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) {//如果空链表则 将头尾指向 新节点 并后继前驱节点设置为NULLlist->head = list->tail = node;node->prev = node->next = NULL;} else {//否则将节点的前驱节点设置为原来的尾部节点node->prev = list->tail;//由于追加到尾部，后继节点为NULLnode->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: %sn", listNodeValue(n));}更多redis知识请关注redis入门教程栏目。以上就是Redis中的双端链表实现的详细内容，更多请关注小潘博客其它相关文章！