adlist是一个普通的双向链表

为什么叫adlist？

image.png
1553417242987884.png

redis作者算是首创了这种命名风格，axxxxx，后面我们还会看到类似的文件命名方式，意即“一个xxxxx”。

虽然是普通的链表，但Redis的adlist绝对也是C下双向链表的实现范式。

基本结构和方法的原型声明与定义(adlist.h)

image.png
1553418911476939.png

节点的定义，一前一后两个指针，void*的值以适配所有数据类型

image.png
1553419116552078.png

迭代器的定义，其中direction域用于指示遍历方向，用迭代器所带来的解耦在后面会明显体现出来

image.png
1553419282440517.png

一个双向链表的所有元信息集成于list中

dup为复制链表的方法；free为释放节点数据域（value）的方法；match方法用于指明在链表中搜索某个节点时判断是否匹配到。常规类型显然是不需要这些方法的，只有对于某些非原生类型需要指定这些方法。

head、tail分别是链表的头尾指针，len指示链表的长度。

想想自己曾写过的链表有这种设计吗？

下面是一些宏函数，非常简单但是非常实用

image.png
1553419889629353.png

下面是所有方法的原型声明

image.png
1553420059224731.png

最后注意这两个宏，这两个宏用于指明迭代器的遍历方向

image.png
1553420183361141.png

实现(adlist.c)

image.png
1553420472959544.png

整个实现唯一的依赖就是zmalloc，zmalloc用于redis的内存管理，使用时与glibc原生的malloc一样，后面会进行剖析

image.png
1553420794685555.png

创建一个链表结构并做一些初始化，此时链表中还没有任何节点

image.png
1553421046425811.png

释放整个链表，包括释放每个节点的数据域，此时free方法若是不为空则会调用free去释放数据域，释放完数据域后再释放节点本身

image.png
1553421164538571.png

在头部插入一个节点，不多说

image.png
1553421310285059.png

在尾部插入一个节点，不多说

image.png
1553421363261646.png

在链表的指定节点的前或后插入一个新节点，入参after若不为0则在old_node后面插入，否则在前面。若是old_node本身是头或尾节点时，对应的前插或后插需要更新相应的头尾，同时要检查新插入节点的前后节点的存在性，并对指针进行相应更行。这段代码也是写得相当精炼了，非常干净漂亮，大多数人写这个过程会冗余不少判断。

image.png
1553421764846887.png

删除指定节点，注意节点本身是头尾的时候应该更新list的head或tail，同时只要是删除操作就应考虑是否需要用free方法去释放数据域，最后调节链表的长度。

image.png
1553421928792582.png

获取一个迭代器时通过direction参数来确定是正向迭代器还是反向迭代器，正向迭代器从头部开始顺序遍历，反向迭代器从尾部开始逆序访问；

释放迭代器可以直接zfree；

值得注意的是，这里的迭代器是左开右开区间

image.png
1553422104507228.png

将迭代器重新定位到头部或尾部，并且会直接对迭代器的方向进行修改

image.png
1553422394922054.png

返回迭代器的所指向的下一个节点并且迭代器往后（或往前）走一步，要注意一个迭代器的初始next指针指向head或者tail节点

image.png
1553430122284899.png

同数组下标一样定位到链表中某个节点，若index >= 0，则head节点为index = 0，head->next index = 1，以此类推；若index < 0，tail节点为index = -1，tail->prev为 index = -2，以此类推；若index超出范围则返回NULL。

image.png
1553430352242295.png

链表的右旋操作，即把尾节点移到链表头部

如果什么时候你需要用到一个双向链表，别忘了这儿有个现成的轮子~