当前位置：首页 > 问答 > 正文

Redis源码里链表到底咋操作的，来一起扒一扒那些细节和机制

畅苗
问答
2026-01-11 15:19:06
3

Redis的链表实现非常经典，它没有使用C++标准库中的std::list，而是自己用C语言重新造了一个“轮子”，这个轮子设计得非常精巧，兼顾了功能性和效率，我们主要来看源码中的adlist.h和adlist.c这两个文件。

链表的结构：三个部分拼成一个整体

Redis的链表不是一个简单的结构体，它由三个部分巧妙组合而成：链表本身（list）、链表节点（listNode）、链表迭代器（listIter）。

链表节点（listNode）： 这是链表最基本的单位，源码里定义,每个节点都包含三个指针：
- *prev：指向前一个节点。
- *next：指向后一个节点。
- *value：这是一个万能指针（void*），它可以指向任何类型的数据，这是Redis链表能存储各种数据类型（字符串、整数、甚至另一个复杂对象）的关键，它不关心具体存的是什么,只负责保管这个指针。
链表（list）： 这个结构体就像是链表的“管理员”或“大脑”，它并不直接存储数据，而是通过持有两个指针（*head和*tail）来管理所有的节点，除此之外,它还记录了几个非常重要的信息：
- *head 和 *tail：分别指向链表的头节点和尾节点，因为有尾指针，所以在链表末尾添加元素变得非常快，是O(1)时间复杂度。
- len：记录链表当前的节点数量，这个设计非常实用，当我们想获取链表长度时，不需要从头到尾遍历一遍计数，直接访问len成员就行了，这也是O(1)的时间复杂度，这是一个典型的“用空间换时间”的优化。
- dup函数指针：这是一个用于“复制”节点值的函数指针。
- free函数指针：这是一个用于“释放”节点值的函数指针。
- match函数指针：这是一个用于“比较”两个节点值是否相等的函数指针。最后这三个函数指针是Redis链表设计的精髓之一，它们让这个链表变成了一个“多态”的容器，因为节点值只是个void*指针，链表本身不知道如何复制、释放和比较它，通过让用户（也就是Redis的其他模块）在创建链表时传入自定义的这三个函数，链表就具备了处理任何数据类型的能力，如果存储的是动态分配的字符串，free函数就可以指定为free；如果存储的是一个复杂结构体,就可以自定义一个函数来释放它占用的所有内存。
链表迭代器（listIter）： 这是为了安全、方便地遍历链表而设计的，它保存了当前遍历的方向（direction，可以是从头到尾或从尾到头）和当前指向的节点（*next），使用迭代器遍历，可以避免在遍历过程中因误操作而修改了原始的next指针,导致遍历出错。

核心操作：增删改查的细节

创建（Create）： 创建一个新链表就是初始化一个list结构体，把head和tail都设为NULL，len设为0，并根据需要设置dup，free，match函数。
插入（Insert）： Redis提供了丰富的插入API，比如在链表头插入（listAddNodeHead）、在链表尾插入（listAddNodeTail）、在某个特定节点前后插入（listInsertNode）,这些操作的核心步骤都类似：
1. 为新节点分配内存。
2. 调整新节点及其前后节点的prev和next指针，像扣链条一样把新节点“链入”指定位置。
3. 更新链表“管理员”（list结构体）的head或tail指针（如果插入位置是头部或尾部的话）。
4. 将链表的len（长度）加1。由于有tail尾指针,在尾部插入的效率极高。
删除（Delete）： 删除节点（listDelNode）的过程是插入的逆过程：
1. 调整被删除节点的前后节点的指针，让它们“越过”被删除节点直接相连，把节点从链表中“摘除”。
2. 如果配置了free函数,就用它来释放节点值所占的内存。
3. 释放被删除节点本身的内存。
4. 将链表的len减1。
查找（Search）： 查找（listSearchKey）操作需要遍历链表，这时，前面提到的match函数指针就派上用场了，遍历时，会用用户自定义的match函数来比较当前节点的值和目标值是否相等，因为链表不支持索引，查找的平均时间复杂度是O(n)。
复制（Duplicate）： 整个链表的复制（listDup）函数充分展示了dup函数指针的威力,它会：
1. 创建一个新的空链表，并继承原链表的dup，free，match函数。
2. 遍历原链表的每一个节点。
3. 对每个节点，使用新链表的dup函数来“复制”一份节点值，如果dup函数为NULL，则简单地复制值的指针（浅拷贝）。
4. 将复制得到的新值创建一个新节点，添加到新链表的末尾。这样,我们就得到了一个深度或浅度可控的链表副本。