链表作为最基础的数据结构，在许多高级语言上已经有了很好的实现。由于redis采用C语言编写，需要自己实现链表，于是redis在adlist.h定义了链表类型。作者对于这部分没什么好说，源码比较简单，如果这方面没有接触过的话，作者也耐心地推荐了几本书供参考。为了提高效率，这里的链表指的是双向链表，使得某一个元素访问它的前驱与后继的时间复杂度均为O（1）。
不多说，进入正题，首先可以看到节点的数据结构的代码如下：
typedef struct listNode {
struct listNode *prev; //前驱节点
struct listNode *next; //后继节点
void *value; //值
} listNode;
C语言没有泛型，但是链表又要存储各种类型的数据，所以这里使用了void指针。由于指针只在编译器级别进行检查，在指令级别是没有类型的，所以这里是OK的。这里的value*指向真正的值存储空间。
按理说使用上面的结构已经可以实现一个简单的链表，redis为了更加简便的使用链表，使用list结构体对节点进行了封装。
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;
使用C语言实现面向对象编程的关键是定义函数指针作为接口，在使用时进行实现，这里定义了三种方法指针，分别用于类型的拷贝（在链表拷贝时调用），类型的释放（在链表释放时调用），类型的比较（类似于C++的运算符重载，用于比较类似的大小），这里的链表定义的写法值得好好学习一下。
使用以上结构，redis存储一个简单的链表示意图如下：
这里可以看到，redis实现的是无环链表，因为首元素的前驱是NULL。这样设计的理由是list已经持有了首元素和尾元素的指针，无需另外在首尾之间组成回路。这张图已经很明显的展示了链表的工作状态，下面对链表的操作的讨论仅以链表插入为例子来进行分析：
list *listAddNodeTail(list *list, void *value)
{
listNode *node; //定义保存值的节点 if ((node = zmalloc(sizeof(*node))) == NULL) //为这个新的节点进行分配空间
return NULL;
node->value = value;
if (list->len == ) { //链表为空的时候
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++;
return list;
}
进行插入的过程比较容易，先定义出节点元素，然后根据链表的当前节点数进行不同的操作：当链表为空时，将list对应域指向node,而当链表不为空时，先完成新节点的成员赋值，然后再更改list的tail域等等，这里一定要注意的是双向列表的节点改变，要留心prev与next的值是否改变，而且新旧节点改变的顺序一定不能错，这个虽然简单，但是还是比较考验基本功的。
总结：可以看出，一些知名的软件，底层还是最基础的东西，并没有什么黑科技，所以掌握好基础真的很重要。作者对这一章描述的比较简单，也就没什么好讲的了。希望以后可以继续坚持写博客。