本系列文章阅读的源码都是Redis-3.0.3版本,编译时使用的是libc库。
链表是常用常见的数据结构，是数据结构课程中比较基础，相对好理解的一种。c语言中没有内置链表数据结构，Redis自己构建了链表adlist。
adlist简介Redis中的链表叫adlist（Agenericdoublylinkedlistimplementation一个通用的双端链表实现）,和普通单链表相比，它的方向可以向前或者向后，这是由于数据结构中定义了next和prev两个指针决定的，下面看下它的数据结构实现。
//链表中的结点结构定义，双向链表，多个listNode结构就组成链表typedefstructlistNode{structlistNode*next;//next指针，指向该结点的下一个结点structlistNode*prev;//prev指针，指向本结点的上一个结点void*value;//void*类型的数据域}listNode;//list持有链表，操作方便typedefstructlist{structlistNode*head;//head指针指向链表头部structlistNode*tail;//tail指针指向链表尾部void*(*dup)(void*ptr);//自定义的复制函数，如果不定义，默认策略的复制操作会让原链表和新链表共享同一个数据域void(*free)(void*ptr);//自定义free操作int(*match)(void*ptr,void*key);//search操作的时候比较两个value是否相等，默认策略是比较两个指针的值unsignedlonglen;//记录链表的长度，获取长度操作可以O(1)返回}list;adlist相关函数listCreate新建链表
新建一个链表，函数内容如下，返回一个list类型的指针，函数中分配一个list结构用于存储后续新建的链表相关信息，最开始还没建立链表时，相关指针都置为NULL，长度为0，
list*listCreate(void){structlist*list;//分配内存if((list=zmalloc(sizeof(*list)))==NULL)returnNULL;//初始化属性list-head=list-tail=NULL;list-len=0;list-dup=NULL;list-free=NULL;list-match=NULL;returnlist;}
在新建后续链表结点时，adlist提供了两种方式，一种是在第一个结点之前插入新结点；一种是在最后一个结点之后插入新结点。
头结点之前插入新结点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;node-prev=node-next=NULL;//添加结点到非空链表}else{node-prev=NULL;node-next=list-head;list-head-prev=node;list-head=node;}//更新链表结点数list-len++;returnlist;}
函数中value指针，是你要插入的结点中对应的value值。在头结点，插入新结点时，如果原来的链表是空表，则head，tail都指向该新结点，但该新结点的prev和next都是NULL。如果原来的结点不是空表，则就需要在头结点之前插入该新建的node结点，则该新结点的next就是之前的list-head结点,原来的list-head结点的prev结点，就指向现在的node的结点，list的头结点改为指向现在的新结点node，相关的指针变动就完成了。注意后三行代码中，这句list-head=node;，list的haed指针指向必须放在最后进行调整，否则就会出问题，读者可以试着调整这三句，在纸上画图更容易理解，下面也有图片供参考理解：
尾结点之后插入新结点从链表外部插入新结点，具体指针变化如上面头插入类似，主要还是list中head，tail及新结点及关联结点的prev,next指针值变化。
list*listAddNodeTail(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;node-prev=node-next=NULL;//目标链表非空}else{node-prev=list-tail;node-next=NULL;list-tail-next=node;list-tail=node;}//更新链表节点数list-len++;returnlist;}迭代器
迭代器类似于c++中的STL容器的iterator，也像C中数组的坐标自增1或减1，从而指向另一个元素或结点，因为链表是结点相互链接，知道一个结点，就可以遍历到整个双端链表中的任何元素，adlist中的迭代器结构如下：
typedefstructlistIter{//当前迭代到的节点listNode*next;//迭代的方向intdirection;}listIter;
其中，direction的值为下面两种，从头到尾遍历链表或者从尾至头遍历链表。
//从表头向表尾进行迭代#defineAL_START_HEAD0//从表尾到表头进行迭代#defineAL_START_TAIL1
创建迭代器函数,参数为list指针和遍历方向，返回listIter迭代器指针。
listIter*listGetIterator(list*list,intdirection){//为迭代器分配内存listIter*iter;if((iter=zmalloc(sizeof(*iter)))==NULL)returnNULL;//根据迭代方向，设置迭代器的起始节点if(direction==AL_START_HEAD)iter-next=list-head;elseiter-next=list-tail;//记录迭代方向iter-direction=direction;returniter;}
该函数中新建了adlist迭代器，并确定next最开始指向链表头结点还是链表尾结点。迭代器生成后，得有指向下一个结点位置的操作，adlist中有了listNext函数，根据上面函数中的direction方向来决定下一个结点。
listNode*listNext(listIter*iter){listNode*current=iter-next;if(current!=NULL){//根据方向选择下一个节点if(iter-direction==AL_START_HEAD)//保存下一个节点，防止当前节点被删除而造成指针丢失iter-next=current-next;else//保存下一个节点，防止当前节点被删除而造成指针丢失iter-next=current-prev;}returncurrent;}
注意该函数参数是迭代器，但返回却为结点指针，通过该值就能得到该结点中的值。
代码验证自己在src的目录下新建tests目录，包含adlist.h头文件进行简单验证，本次验证先简单的listnode中存储的是int值，后续再存储字符串进行复杂一点的验证。简单代码验证如下：
#includestdio.h#include"../adlist.h"intmain(intargc,char*argv[]){structlist*phead=listCreate();//从链表尾部插入新结点intnum1=;phead=listAddNodeTail(phead,num1);intnum2=;listAddNodeTail(phead,num2);//从链表头部插入新结点intnum3=,num4=;listAddNodeHead(phead,num3);listAddNodeHead(phead,num4);//用指针直接遍历链表，并打印链表中每个结点的地址和结点中存储的值printf("Printeachnodeaddressandvalue:\n");structlistNode*ptemp=phead-head;while(ptemp){printf("node:%p,value:%d\n",ptemp,*(int*)(ptemp-value));ptemp=ptemp-next;}//用迭代器遍历链表，并打印结点中存储的值printf("////////////////////////\n");listIter*pIter1=listGetIterator(phead,AL_START_HEAD);listNode*tempnode=listNext(pIter1);while(tempnode){printf("%d\n",*(int*)(tempnode-value));tempnode=listNext(pIter1);}//记得要释放zmalloc申请的空间listReleaseIterator(pIter1);listRelease(phead);return1;}
上述代码在linux中编译通过后，执行结果，两种方式遍历输出的结点存储值是一样的，另外保持良好习惯，记得要释放申请的内存。
参考：
Redis设计与实现