作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（链表）（一）https://developer.aliyun.com/article/1471148

核心方法源码分析（adlist.c）

头文件引入

在C语言的代码中，预处理器指令部分起到了至关重要的作用。这部分代码完成了对三个头文件的引入，分别是：

复制代码

#include <stdlib.h>
#include "adlist.h"
#include "zmalloc.h"

<stdlib.h>：这是C语言的标准库头文件，它包含了诸如内存管理、程序控制以及类型转换等功能的函数和宏定义。通过引入这个头文件，我们可以方便地使用malloc、free、exit等标准库函数，为程序提供基础且强大的支持。
"adlist.h"：通过引入这个头文件，可以利用其中定义的数据结构、函数原型或宏，从而简化列表相关操作的实现。
"zmalloc.h"：引入这个头文件后，可以使用其中提供的特定内存分配和释放机制，这些机制可能具有更好的错误处理、内存跟踪或其他高级功能，从而增强程序的健壮性和性能。

listCreate：创建一个新的空链表

时间复杂度：O(1)

下面的源码是创建新链表的函数listCreate的实现。该函数返回list指针类型，不接受任何参数。以下是对源码的详细注释和解释，帮助您清晰地了解源码的含义和实现原理。

复制代码

// 创建新链表的函数，返回链表结构体的指针
list *listCreate(void)
{
    // 声明了一个list结构体的指针list。struct list 应该是在adlist.h头文件中定义的，它定义了链表的结构。
    struct list *list;
   // 使用 zmalloc 函数为 list 结构体分配内存。zmalloc是Redis提供的内存分配函数，它在内存分配失败时会返回 NULL。sizeof(*list) 计算 list 指针所指向的结构体的大小。
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL; //如果内存分配失败，函数会返回 NULL。    
    // 这里初始化了链表的头指针 head 和尾指针 tail 为 NULL，并设置链表的长度 len 为 0。这表示新创建的链表是空的。    
    list->head = list->tail = NULL;
    list->len = 0; // 初始长度为0
    // 设置复制、释放和匹配函数为 NULL
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

总结一下，listCreate 函数的主要功能是创建一个新的、空的链表，并返回其指针。如果内存分配失败，它会返回 NULL。当不再需要已创建的列表时，应使用listRelease()函数来释放其占用的内存。在调用listRelease()之前，列表中每个节点的私有值需要由用户自行释放，或者可以通过listSetFreeMethod函数来设定一个自动释放这些私有值的方法。

listRelease：释放整个列表

时间复杂度：O(N) ，N为链表长度

listRelease 函数具有高度的可靠性，它确保成功释放给定的链表及其所包含的所有节点，不会出现失败的情况。通过调用该函数，可以有效地回收链表占用的内存资源，确保程序的稳定运行。

复制代码

/*  
 * Free the whole list.
 * This function can't fail. 
 */
void listRelease(list *list)
{
    //传入的list指针是否为NULL。如果是NULL，函数会直接返回，不执行任何操作。
    if (!list) // 避免了在空指针上执行操作，这可能会导致未定义行为或程序崩溃。
        return;
    // 调用listEmpty函数来释放链表中的所有节点，逐个释放每个节点所占用的内存。
    listEmpty(list);
    // 使用zfree函数来释放list结构体本身所占用的内存
    zfree(list);
}

listEmpty：移除所有的元素，但是不释放自己本身

时间复杂度：O(1)

在深入探讨listRelease方法的实现时，我们注意到其中调用了listEmpty方法。为了更全面地理解整个链表的内存释放过程，接下来我们将仔细研究并分析listEmpty方法的实现原理和运行流程。下面的源码就是针对于实现原理和流程进行分析，有了对应的源码和注释，相信你可以从底层更加清晰的认识listEmpty的实现原理。

复制代码

/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)  
{  
    // 获取链表的长度  
    unsigned long len;  
    // 定义当前节点和下一个节点的指针  
    listNode *current, *next;  
      
    // 将当前节点指针指向链表的头节点  
    current = list->head;  
      
    // 将链表长度赋值给len变量，方便后续遍历  
    len = list->len;  
      
    // 循环遍历链表，直到所有节点都被处理  
    while(len--) {  
        // 将下一个节点指针指向当前节点的下一个节点  
        next = current->next;  
          
        // 如果链表定义了释放节点值的函数，则调用该函数释放当前节点的值  
        if (list->free) list->free(current->value);  
          
        // 释放当前节点所占用的内存  
        zfree(current);  
          
        // 将当前节点指针指向下一个节点，准备处理下一个节点  
        current = next;  
    }  
      
    // 将链表的头节点和尾节点指针置为NULL，表示链表为空  
    list->head = list->tail = NULL;  
      
    // 将链表长度置为0，表示链表没有节点  
    list->len = 0;  
}

listAddNodeHead：插入新节点到表头

时间复杂度：O(1)

函数的目的通过插入新节点到表头，我们根据需要修改链表的结构和内容。无论是将新节点添加到链表的开头，还是在特定节点的前后位置插入，都能轻松实现。同时，通过返回更新后的链表头节点指针，我们可以方便地访问和操作整个链表。

参数：

list：指向列表的指针
value：要添加到新节点的值（作为指针）

返回值：

成功时返回更新后的列表指针
出错时返回NULL

下面便是源码的分析和解释说明：

复制代码

// 定义一个名为 listAddNodeHead 的函数，该函数接受一个指向 list 结构的指针和一个 void 类型的指针作为参数。  
// 函数返回一个指向 list 结构的指针。  
list *listAddNodeHead(list *list, void *value)  
{  
    // 定义一个指向 listNode 结构的指针 node。  
    listNode *node;  
  
    // 使用 zmalloc 函数为 listNode 分配内存，并将返回的地址赋值给 node。  
    // 如果内存分配失败，zmalloc 会返回 NULL。  
    if ((node = zmalloc(sizeof(*node))) == NULL)  
        // 如果内存分配失败，则返回 NULL。  
        return NULL;  
  
    // 将传入的 value 赋值给新节点的 value 字段。  
    node->value = value;  
  
    // 调用 listLinkNodeHead 函数，将新节点添加到链表的头部。  
    listLinkNodeHead(list, node);  
  
    // 返回更新后的链表指针。  
    return list;  
}

我们需要向给定的列表头部添加一个新节点，该节点包含特定的“值”。在此过程中，指针将作为关键参数进行传递。若在执行过程中遇到任何错误，函数将立即返回NULL，且不会执行任何对原列表的修改操作，以确保列表的完整性。一旦操作成功，函数将返回传递给它的原始“列表”指针，以便调用者能够继续利用更新后的列表。

listAddNodeTail：插入新节点到表尾

时间复杂度：O(1)

函数的目的通过插入新节点到表尾，我们根据需要修改链表的结构和内容。下面便是源码的分析和解释说明：

参数：

list：指向列表的指针
value：要添加到新节点的值（作为指针）

返回值：

成功时返回更新后的列表指针
出错时返回NULL

复制代码

// 函数定义：将一个新节点添加到列表的尾部，并返回更新后的列表指针。  
list *listAddNodeTail(list *list, void *value)  {  
    // 声明一个指向listNode结构的指针node，用于存储新节点的地址  
    listNode *node;  
    // 使用zmalloc函数为新节点分配内存，并将返回的地址赋值给node  
    // 如果内存分配失败，zmalloc将返回NULL  
    if ((node = zmalloc(sizeof(*node))) == NULL)  
        // 如果内存分配失败，则返回NULL，不执行任何操作  
        return NULL;  
    // 将传入的value赋值给新节点的value字段  
    node->value = value;  
    // 调用listLinkNodeTail函数，将新节点添加到列表的尾部  
    listLinkNodeTail(list, node);  
    // 返回更新后的列表指针  
    return list;  
}

在列表中的尾部添加一个全新的节点，这个新节点应持有指定的“Value”指针作为其内容。如果在执行过程中出现任何错误，函数将立即返回NULL，并且不会进行任何对原列表的修改，以确保列表的完整性。一旦操作成功完成，函数将返回传递给它的原始“list”指针，以便调用者能够继续利用更新后的列表。

listLinkNodeHead：将新节点添加到链表

时间复杂度：O(1)

将预先分配好的节点添加至列表的起始位置，实现节点的头部插入操作。

复制代码

// 函数用于将一个节点链接到链表的头部  
void listLinkNodeHead(list* list, listNode *node) {  
    // 如果链表为空（即长度为0）  
    if (list->len == 0) {  
        // 将新节点设置为链表的头节点和尾节点  
        list->head = list->tail = node;  
        // 因为链表只有一个节点，所以该节点的prev和next都指向NULL  
        node->prev = node->next = NULL;  
    } else {  
        // 如果链表不为空，那么将新节点的prev指向NULL（因为它是头部节点）  
        node->prev = NULL;  
        // 将新节点的next指向当前的头节点  
        node->next = list->head;  
        // 将当前头节点的prev指向新节点，形成双向链表的链接  
        list->head->prev = node;  
        // 将链表的头节点更新为新节点  
        list->head = node;  
    }  
    // 无论链表是否为空，都将链表的长度加1  
    list->len++;  
}

链表为空的情况：

如果链表为空（list->len == 0），说明之前没有节点，新节点不仅会成为头节点，也会成为尾节点。
将list->head和list->tail都指向新节点node。
由于链表只有一个节点，该节点的prev和next指针都应该指向NULL。

链表不为空的情况：

初始化新节点的prev为NULL，因为它即将成为新的头节点。
将新节点的next指向当前的头节点list->head。
更新当前头节点的prev指针，使其指向新节点，确保双向链表的连接正确。
更新链表的头节点指针list->head，使其指向新节点。

链表长度更新：

无论链表之前是否为空，在插入新节点后，链表的长度都会增加1，因此list->len需要加1。

listDelNode：从链表中删除给定的节点

时间复杂度：O(N)，N为链表长度

从给定的列表中移除特定的节点，并释放该节点的内存。若提供了自由回调函数，则利用该函数来释放节点所持有的值。此函数确保执行成功，不会出现失败的情况。

复制代码

// 函数定义：从列表中删除一个节点，并释放相关内存  
void listDelNode(list *list, listNode *node)  
{  
    // 调用listUnlinkNode函数，从列表中解除该节点的链接  
    listUnlinkNode(list, node);  
    // 如果列表的free字段不为空（即存在一个用于释放节点值的回调函数）  
    if (list->free)   
        // 调用该回调函数，释放节点中存储的值所占用的内存  
        list->free(node->value);  
      
    // 调用zfree函数，释放节点本身所占用的内存  
    zfree(node);  
}

listUnlinkNode：列表中解除该节点的链接

时间复杂度：O(1)

从给定的列表中移除特定的节点，但保留其内存不被释放。这意味着节点仍然存在于内存中，只是不再与列表相关联。

复制代码

// 函数定义：从双向链表中移除一个节点，但不释放其内存  
void listUnlinkNode(list *list, listNode *node) {  
    // 如果该节点有前一个节点  
    if (node->prev) {  
        // 将前一个节点的next指针指向当前节点的下一个节点  
        node->prev->next = node->next;  
    } else {  
        // 否则，当前节点是头节点，将列表的头指针指向当前节点的下一个节点  
        list->head = node->next;  
    }  
      
    // 如果该节点有下一个节点  
    if (node->next) {  
        // 将下一个节点的prev指针指向当前节点的前一个节点  
        node->next->prev = node->prev;  
    } else {  
        // 否则，当前节点是尾节点，将列表的尾指针指向当前节点的前一个节点  
        list->tail = node->prev;  
    }  
      
    // 将当前节点的next和prev指针都设置为NULL，表示它已经从链表中移除  
    node->next = NULL;  
    node->prev = NULL;  
      
    // 减少列表的长度计数  
    list->len--;  
}

通过执行此操作，您可以重新利用该节点，或者将其添加到其他列表中，而无需再次分配内存。此功能确保从列表中安全地移除节点，同时保持其内存完整性。

最后总结

由于篇幅过程，因此其他的函数就不一一列举了，在这里主要给大家介绍了以上这几个函数，因为它们属于较为核心以及重要的方法。如果大家希望作者完善和继续完成其他的函数还希望大家在评论区沟通和说明，我会努力完成和完善的，文章和学习不容易，希望大家多多支持、点赞和鼓励！

源码来源

链表是Redis实现各种功能的核心组件，诸如列表键的操作、发布订阅机制、慢查询跟踪以及监视器功能，都依赖链表的支持。

链表节点

链表节点的表示通过精心设计的listNode结构体来实现。每个节点不仅包含数据，还具备指向前一个节点和后一个节点的指针，使得Redis的链表成为双向链表，提供了更加灵活的遍历和操作方式。

列表结构

整个链表由list结构体代表，包含指向链表头节点和尾节点的指针，以及记录链表长度的信息。这种结构化的管理方式使得链表的操作更加高效和便捷。

注意，Redis的链表实现特别注重安全性。链表头节点的前置指针和链表尾节点的后置指针都指向NULL，这种设计有效避免了链表中的环形结构，确保了链表操作的安全性和稳定性。

作者推荐 |【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现（链表）（二）

核心方法源码分析（adlist.c）

头文件引入

listCreate：创建一个新的空链表

listRelease：释放整个列表

listEmpty：移除所有的元素，但是不释放自己本身

listAddNodeHead：插入新节点到表头

listAddNodeTail：插入新节点到表尾

listLinkNodeHead：将新节点添加到链表

listDelNode：从链表中删除给定的节点

listUnlinkNode：列表中解除该节点的链接

最后总结

源码来源

链表节点

列表结构

热门文章

最新文章

相关课程

相关电子书

相关实验场景