近期一直尝试用go语言复刻redis，所以开始深入研究redis那些巧妙的数据结构设计与实现，本篇文章将针对redis中链表的设计与实现进行源码级别的分析，希望对你有所启发。
详解redis中链表的设计与实现
链表底层结构的设计
链表是由无数个节点也就是我们常说的listNode构成，每个节点通过前驱和后继节点指针维护其前驱和后继节点信息：
对应的我们也给出redis中链表节点listNode 的源码，它位于adlist.h的定义中，可以看到它通过prev指针和next指针分别管理当前节点的前驱节点和后继节点，然后通过value指针维护当前节点的值，由这一个个节点的串联构成双向链表：
复制
typedef struct listNode {
//指向前驱节点
struct listNode *prev;
//指向后继节点
struct listNode *next;
//维护当前节点的值的指针
void *value;
} listNode;1.2.3.4.5.6.7.8.
双向链表需要一个头指针和尾指针管理首尾节点，从而实现后续灵活的头插法和尾插法的操作，所以在设计双向链表的时候，我们就需要一个head和tail指针管理链表的首尾节点。同时，为了实现O(1)级别的长度计算，在元素添加或者删除操作的时候，我们还需要一个len字段记录当前链表的长度：
而redis中双向链表的结构体list 也是同理：
复制
typedef struct list {
//头节点指针
listNode *head;
//尾节点指针
listNode *tail;
//......
//链表长度
unsigned long len;
} list;1.2.3.4.5.6.7.8.9.
了解了基本的数据结构，我们再来说说链表的初始化，redis中的双向链表会为其分配一块内存空间，然后将头尾节点的指针设置为空，长度初始化为0：
对应的我们给出双向链表初始化的源码即位于adlist.c的listCreate函数，它完成空间分配和指针、长度初始化之后返回这个链表的指针：
复制
list *listCreate(void)
{
//为list结构体分配内存空间
struct list *list;
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
//头尾指针初始化设置为空
list->head = list->tail = NULL;
//链表长度设置为0
list->len = 0;
//......
return list;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.
节点头插法的实现
通过上文我们了解了链表的基本数据结构，接下来我们就来聊聊链表的第一个操作，也就是头插法，这个操作就是将最新的节点插入的链表的首部，我们以初次插入为例，此时链表全空，双向链表初始化节点之后，就会让链表的头尾指针指向这个node，然后长度自增为1：
若非第一次操作，则初始化一个新节点之后，让这个节点指向原有的头节点，最后让原有的头节点作为新节点的后继即可：
图片
对此我们也给出头插法的源码，可以看到它会传入当前需要操作的链表和新节点的value指针完成节点生成和头插工序，对应的源码操作细节和上述讲解大体一致，读者可自行参阅：
复制
list *listAddNodeHead(list *list, void *value)
{
//初始化node节点内存空间
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
//value指针指向传入的值
node->value = value;
//如果链表长度为0，则让首尾节点指向这个node，然后node前驱和后继节点为空
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
//节点的前驱指向空，后继节点指向原有的头节点，完成后再让原有的头节点作为新节点的后继节点
//最后head指针指向当前node
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
//维护一下链表的长度+1
list->len++;
return list;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.
尾插法的实现
尾插法就是将最新节点插入到链表末尾，初次插入和头插法一致，即头指针head和尾指针tail都指向最新node节点，这里就不做赘述。 我们重点说说常规操作的尾插法，双向链表在进行尾插法时步骤如下：
新节点前驱节点指向原有尾节点。原有的尾节点后继指针指向新节点。修改tail指针指向，让新节点作为最新的尾节点。
尾插法的函数为listAddNodeTail，入参为要进行操作的list指针和value值，操作步骤的上图表述基本一致，读者可结合注释自行参阅：
复制
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
//分配node内存空间
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
//node的value指针指向value
node->value = value;
//如果长度为0，则首尾指针指向这个node
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
//新节点的前驱节点指向尾节点，然后让原有尾节点指向新节点，最后让tail指针指向新节点
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
//长度信息维护一下
list->len++;
return list;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.
指定节点插入
该函数会传入修改前驱后继关系的节点，如果希望将新节点n插入到旧节点后面，则会让新节点n的前驱指向原有节点，后继节点指向原有节点的后继，最后让新节点的前驱后继节点指向插入的新节点n:
同理插入前面也很节点后添加差不多，这里就不多赘述，对此我们给出listInsertNode的源码，可以看到它传入需要进行操作的list指针，再传入需要维护新关系的old_node指针和需要插入的value，将value封装为node之后，如果after为1则执行上述所说的old_node后节点插入操作：
node的前驱指向old_node。node后继指向old_node的后继。old_node的next指针和old_node的后继节点都指向node。
对应的源码如下，读者可参考笔者上述图解并结合源码注释了解整个插入过程：
复制
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
//节点初始化并设置value
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
//如果after为1则将新节点插入到old_node后面
if (after) {
//node前驱指向old_node，node指向old_node的后继
node->prev = old_node;
node->next = old_node->next;
//如果old_node是尾节点，则让tail指向新插入的node
if (list->tail == old_node) {
list->tail = node;
}
} else {
//将新节点插入到old_node前面
node->next = old_node;
node->prev = old_node->prev;
//如果old_node是头节点，则修改head指向，让其指向新节点
if (list->head == old_node) {
list->head = node;
}
}
//将node原有的前驱后继节点指向当前node维护的前驱和后继节点
if (node->prev != NULL) {
node->prev->next = node;
}
if (node->next != NULL) {
node->next->prev = node;
}
//维护一下长度
list->len++;
return list;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.
获取指定位置的元素
双向链表支持基于索引查找指定位置的元素，操作时间复杂度为O(n)，我们以从头查找为例，如果希望查找索引2的元素，也就是第3个元素，它就会从head开始跳越2条，由此走到第3个节点的位置并返回这个节点的指针：
对应我们给出listIndex的源码，可以看到如果传入的index为负数，则说明调用者要从后往前找，假设我们传入-2也就是要找到倒数第2个元素，最终取正计算得到1，这也就意味着我们只需从尾节点跳1下就能得到倒数第2个元素，而index若为正数则是顺序查找，原理如上图解析，这里就不多赘述了，读者可自行查阅listIndex函数及其源码：
复制
listNode *listIndex(list *list, long index) {
listNode *n;
//如果小于0，说明从后往前照
if (index < 0) {
//将负数转为正数，例如传入-2，也就找倒数第2个元素，转为正为1，也就是往前1跳，返回这个node
index = (-index)-1;
n = list->tail;
while(index-- && n) n = n->prev;
} else {
//说明从前往后照，跳n跳即可得到对应元素
n = list->head;
while(index-- && n) n = n->next;
}
return n;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.
删除指定位置的元素
最后一个就是链表删除操作了，操作比较简单，让被删除节点的前驱和后继节点构成关联关系，然后释放当前被删节点，然后减小一下长度即可：
对应的源码如下，读者可自行参阅学习：
复制
void listDelNode(list *list, listNode *node)
{
//如果node前驱有节点，则让这个节点指向被删除节点的后继
//反之说明这个节点是头节点，则让head指向这个后继节点
if (node->prev)
node->prev->next = node->next;
else
list->head = node->next;
//如果这个节点有后继节点，则让这个后继的prev指向被删节点的前驱
//反之说明被删的是尾节点，则让tail指针指向被删节点的后继
if (node->next)
node->next->prev = node->prev;
else
list->tail = node->prev;
//释放被删除节点的内存空间，并减小链表长度
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.
小结
自此我们将redis底层的双向链表的设计与实现的源码进行的深入分析，从中了解到redis双向链表数据结构设计和节点操作的实现细节，希望对你有所帮助。
