写在文章开头

近期一直尝试用go语言复刻redis，所以开始深入研究redis那些巧妙的数据结构设计与实现，本篇文章将针对redis中链表的设计与实现进行源码级别的分析，希望对你有所启发。

Hi，我是 sharkChili ，是个不断在硬核技术上作死的技术人，是 CSDN的博客专家 ，也是开源项目 Java Guide 的维护者之一，熟悉 Java 也会一点 Go ，偶尔也会在 C源码 边缘徘徊。写过很多有意思的技术博客，也还在研究并输出技术的路上，希望我的文章对你有帮助，非常欢迎你关注我的公众号： 写代码的SharkChili 。

因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。

详解redis中链表的设计与实现

链表底层结构的设计

链表是由无数个节点也就是我们常说的listNode构成，每个节点通过前驱和后继节点指针维护其前驱和后继节点信息：

对应的我们也给出redis中链表节点listNode 的源码，它位于adlist.h的定义中，可以看到它通过prev指针和next指针分别管理当前节点的前驱节点和后继节点，然后通过value指针维护当前节点的值，由这一个个节点的串联构成双向链表：

typedef struct listNode {
    //指向前驱节点
    struct listNode *prev;
    //指向后继节点
    struct listNode *next;
    //维护当前节点的值的指针
    void *value;
} listNode;

双向链表需要一个头指针和尾指针管理首尾节点，从而实现后续灵活的头插法和尾插法的操作，所以在设计双向链表的时候，我们就需要一个head和tail指针管理链表的首尾节点。同时，为了实现O(1)级别的长度计算，在元素添加或者删除操作的时候，我们还需要一个len字段记录当前链表的长度：

而redis中双向链表的结构体list 也是同理：

typedef struct list {
    //头节点指针
    listNode *head;
    //尾节点指针
    listNode *tail;
    //......
    //链表长度
    unsigned long len;
} list;

了解了基本的数据结构，我们再来说说链表的初始化，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;
}

节点头插法的实现

通过上文我们了解了链表的基本数据结构，接下来我们就来聊聊链表的第一个操作，也就是头插法，这个操作就是将最新的节点插入的链表的首部，我们以初次插入为例，此时链表全空，双向链表初始化节点之后，就会让链表的头尾指针指向这个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;
}

尾插法的实现

尾插法就是将最新节点插入到链表末尾，初次插入和头插法一致，即头指针head和尾指针tail都指向最新node节点，这里就不做赘述。 我们重点说说常规操作的尾插法，双向链表在进行尾插法时步骤如下：

1. 新节点前驱节点指向原有尾节点。
2. 原有的尾节点后继指针指向新节点。
3. 修改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;
}

指定节点插入

该函数会传入修改前驱后继关系的节点，如果希望将新节点n插入到旧节点后面，则会让新节点n的前驱指向原有节点，后继节点指向原有节点的后继，最后让新节点的前驱后继节点指向插入的新节点n:

同理插入前面也很节点后添加差不多，这里就不多赘述，对此我们给出listInsertNode的源码，可以看到它传入需要进行操作的list指针，再传入需要维护新关系的old_node指针和需要插入的value，将value封装为node之后，如果after为1则执行上述所说的old_node后节点插入操作：

1. node的前驱指向old_node。
2. node后继指向old_node的后继。
3. 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;
}

获取指定位置的元素

双向链表支持基于索引查找指定位置的元素，操作时间复杂度为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;
}

删除指定位置的元素

最后一个就是链表删除操作了，操作比较简单，让被删除节点的前驱和后继节点构成关联关系，然后释放当前被删节点，然后减小一下长度即可：

对应的源码如下，读者可自行参阅学习：

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--;
}

小结

自此我们将redis底层的双向链表的设计与实现的源码进行的深入分析，从中了解到redis双向链表数据结构设计和节点操作的实现细节，希望对你有所帮助。

我是 sharkchili ，CSDN Java 领域博客专家，mini-redis的作者，我想写一些有意思的东西，希望对你有帮助，如果你想实时收到我写的硬核的文章也欢迎你关注我的公众号： 写代码的SharkChili 。 因为近期收到很多读者的私信，所以也专门创建了一个交流群，感兴趣的读者可以通过上方的公众号获取笔者的联系方式完成好友添加，点击备注 “加群” 即可和笔者和笔者的朋友们进行深入交流。