本文转载自微信公众号《学Java的小姐姐》，作者0618学Java的。转载本文请联系正在学习Java的小姐姐公众号。前言大家好，我们又见面了。别问为什么，问就是辛苦。爆款更新模式即将开启。链表List在Redis中的应用非常广泛，但是Redis是用C语言写的，底层是双向链表实现的。.我们今天的重点是双向链表。API用法让我们先使用API??。如果你以前用过，可以直接跳到下一节。在lpush的左侧插入数据使用lpush命令将三个字符a、b、c插入到列表的左侧。这里注意顺序，查询结果为c、b、a。下面会解释为什么，先挖个洞。在rpush右侧插入数据使用rpush命令将d和e这两个字符插入到列表中。查询的顺序和我们想的一样，最后两个字符是d和e。删除某条数据，使用lrem命令删除a字符，那么中间的1是什么意思呢？就是count，意思是去掉列表中等于a的元素个数。即如果count>0，则表示从表头到表尾查找，去掉count个等于a的元素。如果count<0，表示从表尾到表头查找，去掉count个等于a的元素。如果count=0，则移除所有等于a的元素，因为它移除了所有，所以无论从表头还是表尾，结果都是一样的。修改某条数据，使用lset命令将mylist下标为1的元素改为dd。原来的列表是c,b,d,e，修改后的结果是c,dd,d,e。看不懂这里的具体逻辑图也没关系。下面将详细解释每个模块。双向链表的定义节点ListNode包括头指针prev、尾指针next和当前值value，如下图所示。每个节点都有两个指针，既可以根据表尾指针从表头找到表尾，也可以根据表头指针prev从表尾找到表头。如果它们相连，则形成一个双向链表。具体代码如下：//定义链表节点的结构typedefstructlistNode{//上一个节点的指针structlistNode*prev;//下一个节点的指针structlistNode*next;//value的指针当前节点的，因为值的类型不同Determinevoid*value;}listNode;整体结构包括头指针head，尾指针tail，整个链表的长度len，以及一些函数（我觉得不重要，有知道的欢迎评论），如下图.头指针head指向整个链表的第一个节点，尾指针tail指向整个链表的最后一个节点。具体代码如下：//定义链表，重新封装链表节点typedefstructlist{listNode*head;//头指针listNode*tail;//尾指针void*(*dup)(void*ptr);//nodecopyfunctionvoid(*free)(void*ptr);//释放节点值functionint(*match)(void*ptr,void*key);//判断两个节点是否相等functionunsignedlonglen;//link列表长度}列表；双向链表的实现创建表头我们创建一个链表结构。首先，我们需要判断是否有空间可供分配。使用zmalloc方法分配空间。如果不能分配，返回NULL。如果可以分配，继续。然后将链表的头节点head和尾节点tail赋值为NULL，len赋值为0，相关函数赋值为NULL。最后返回结果列表。//创建表头，返回值为链表指针list*listCreate(void){structlist*list;//尝试分配空间if((list=zmalloc(sizeof(*list)))==NULL）返回空；//相关属性赋值list->head=list->tail=NULL;list->len=0;list->dup=NULL;list->free=NULL;list->match=NULL;//最终结果返回返回列表；清空表，传入链表指针，先定义当前节点current，使其指向头指针，定义len，使其等于链表的长度。然后循环，每次len减一，定义一个新的节点next，它总是指向当前节点current的下一个节点。如果有值，则释放该节点，当前节点current向后移动，下一个节点也向后移动。直到len为0，释放所有节点，退出循环。最后，赋值链表的头节点head和tail节点tail为NULL，len为0。注意：这里和SDS一样，清除不是直接删除链表，而是删除它的数据，外层链表结构依旧存在。这实际上是惰性删除。voidlistEmpty(list*list){unsignedlonglen;//定义两个节点指针current和nextlistNode*current,*next;//当前节点指针current指向链表的头节点位置，即链表的第一个数据current=list->head;//len为list的长度len=list->len;//开始循环，每次len减1while(len--){//让下一个指针指向先到下一个节点，因为当前节点是直接在最底层释放的，这里不复制就得不到next=current->next;//释放当前节点的值if(list->free)list->free(current->value);//释放当前节点zfree(current);//当前节点等于刚才的下一个节点，即开始向后移动和开始下一个循环current=next;}//释放后，将头指针head和尾指针tail赋值给NULLlist->head=list->tail=NULL;//len赋值0list->len=0;}添加elementstotheheader添加元素到header，首先新建一个node节点，判断是否有内存分配，有则继续，无则返回NULL并退出方法。这里新建的节点是用来存放入参中的值的，所以需要内存。然后将新节点节点的值赋值作为输入参数值。最后还需要调整链表的头指针和尾指针，以及首节点的原指针（看下图，描述的有点乱，不过图一目了然）。最后，将列表的len加1并返回列表。例如，要将节点f插入到链表中，首先将该节点的头指针赋值为null（对应步骤1），然后将新节点的尾指针next指向第一个节点（对应步骤2）)，并设置每个节点的第一个prev指向新节点（对应步骤3），最后链表的头指针head指向新节点（对应步骤4）。这里需要注意的是，第2步和第3步需要在第4步之前，否则会找到第一个节点。具体代码如下：//在头部添加一个元素list*listAddNodeHead(list*list,void*value){listNode*node;if((node=zmalloc(sizeof(*node)))==NULL)returnNULL;node->value=value;//给当前节点赋值//如果当前链表为空if(list->len==0){list->head=list->tail=node;//头尾指针指向本Nodenode->prev=node->next=NULL;//当前节点头尾指针均为null}else{//如果当前链表不为空node->prev=NULL;//新节点的头指针为nullnode->next=list->head;//新节点的尾指针指向原尾指针list->head->prev=node;//原首节点头指针指向新节点list->head=node;//链表头指针指向新节点}list->len++;//链表长度+1returnlist;}向链表尾部添加元素向链表尾部添加元素，首先新建一个node节点，判断是否有分配内存，如果有，继续，否则返回NULL，并退出该方法。这里新建的节点是用来存放入参中的值的，所以需要内存。然后将新节点节点的值赋值作为输入参数值。最后需要调整链表的头指针和尾指针，以及最后一个节点的原指针（见下图，描述的有点乱，但是图一目了然）。最后，将列表的len加1并返回列表。例如，要在链表中插入节点f，首先将该节点的尾指针赋值为null（对应步骤1），然后将新节点的头指针指向最后一个节点（对应步骤2），并设置最后一个节点的next指向新节点（对应步骤3），最后将链表的尾指针tail指向新节点（对应步骤4）。步骤如下：//向尾列表中添加元素*listAddNodeTail(list*list,void*value){//新建节点nodelistNode*node;//尝试分配内存if((node=zmalloc(sizeof(*node)))==NULL)returnNULL;//赋值node->value=value给新节点node;//调整指针if(list->len==0){list->head=list->tail=node;node->prev=node->next=NULL;}else{node->prev=list->tail;node->next=NULL;list->tail->next=node;list->tail=node;}//lenadd1list->len++;returnlist;}插入到链表中某个节点的old_node后面（大于0的在前加，小于0的在后加），加一个newvalue值，先新建一个node节点，判断是否有内存分配，有则继续，没有则返回NULL，退出方法。这里新建的节点是用来存放入参中的值的，所以需要内存。然后根据after的值，判断是在节点old_node前面添加数据，还是在节点old_node后面添加数据，具体就是指针的调整。最后，将len加1并返回列表。//在list的某个位置插入old_node之后（前后）的值list*listInsertNode(list*list,listNode*old_node,void*value,intafter){listNode*node;if((node=zmalloc(sizeof(*node)))==NULL)returnNULL;node->value=value;if(after){//大于0node->prev=old_node;node->next=old_node->next;if(list->tail==old_node){list->tail=node;}}else{//小于0node->next=old_node;node->prev=old_node->prev;if(list->head==old_node){list->head=node;}}if(node->prev!=NULL){node->prev->next=node;}if(node->next!=NULL){node->next->prev=node;}list->len++;returnlist;}Delete从列表中删除节点节点。如果该节点前面有一个节点，则让前一个节点的next指针指向该节点后面的节点地址。实际上是跳过了node节点。如果节点的上一个节点没有，则链表的头指针指向node的下一个节点的地址。同样，如果节点后面还有一个节点，逻辑也是一样的。最后释放待删除节点的节点内存，len减1。//从链表中删除一个节点nodevoidlistDelNode(list*list,listNode*node){//如果该节点前面有一个节点if(node->prev)node->prev->next=node->下一个;elselist->head=node->next;//如果节点前面有节点if(node->next)node->next->prev=node->prev;elselist->tail=node->prev;//释放当前节点node的值if(list->free)list->free(node->value);//释放内存zfree(node);//len-1list->len--;}本文主要内容总结浅谈Redis的list数据类型底层实现双向链表adlist，先利用list的一些API引出双向链表数据结构，再结合源码描述双向链表的代码，包括节点listNode和list的头指针和尾指针，最后针对链表头插入元素、链表尾插入元素的方法进行源码分析列表、删除、修改列表，让其对双向链表有更清晰的认识。如果您觉得文笔还可以，请给我一个赞👍，您的认可是我写作的动力！
