目录
💖 简介
redis 源码版本：3.05.04
如需源码，可官网下载或如下直接下载：
链接：https://pan.baidu.com/s/1vl_8UD30xZry4irsgmbdLQ
提取码：mpds
如有理解不对的地方，欢迎各位指出，大家共同交流和学习。 如有帮助，请点赞加支持！ 送人玫瑰手有余香！🌹🌹🌹
💖源码学习
🏆 listInsertNode函数源码
💚 将给定值插入到指定节点💚
/* 功能：将给定值插入到指定节点之前或之后
* @param list:原链表
* @param old_node:指定节点
* @param value:新节点的值
* @param after:值为0，新节点插入到old_node之前
值为1，新节点插入到old_node之后
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value; //将新增的值，保存到node节点
if (after) { //值为1，新节点插入到old_node之后
node->prev = old_node;
node->next = old_node->next;
if (list->tail == old_node) {//指定节点为原链表尾节点的情况
list->tail = node;
}
} else { //值为0，新节点插入到old_node之前
node->next = old_node;
node->prev = old_node->prev;
if (list->head == old_node) {//指定节点为原链表头节点的情况
list->head = node;
}
}
if (node->prev != NULL) {//新增节点的存在前置节点时，更新前置节点的指针
node->prev->next = node;
}
if (node->next != NULL) {//新增节点的存在后置节点时，更新后置节点的指针
node->next->prev = node;
}
list->len++; //节点个数加1
return list; //返回新的链表
}
🏆 listDelNode函数源码
💚 删除指定节点💚
/* 功能：删除指定节点后
* @param list:原链表
* @param node:指定节点
*/
void listDelNode(list *list, listNode *node)
{
if (node->prev)//如果指定节点存在前置节点，更新前置节点的指针
node->prev->next = node->next;
else
list->head = node->next;
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
}
删除节点的三种情况示意图：
🟣 删除头节点
🟣 删除尾节点
🟣 删除中间节点
🏆 listGetIterator函数源码
💚 创建一个迭代器💚
/* 功能：创建一个迭代器
* @param list:链表
* @param direction:值为0，从表头向表尾遍历
值为1，从表尾向表头遍历
*/
listIter *listGetIterator(list *list, int direction)
{
listIter *iter;
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD) //direction等于0，迭代器从表头向表尾遍历
iter->next = list->head;
else //direction等于1，迭从表尾向表头遍历
iter->next = list->tail;
iter->direction = direction; //记录迭代方向
return iter;
}
其中，AL_START_HEAD和AL_START_TAIL在头文件中定义。如下：
#define AL_START_HEAD 0
#define AL_START_TAIL 1
🏆 listReleaseIterator函数源码
💚 释放迭代器内存💚
/* 功能：释放迭代器内存
* @param iter:迭代器
*/
void listReleaseIterator(listIter *iter) {
zfree(iter); //释放内存
}
🏆 listRewind函数源码
💚 迭代器重新指向表头💚
/* 功能：迭代器重新指向表头
* @param iter:链表
* @param li:迭代器
*/
void listRewind(list *list, listIter *li) {
li->next = list->head;
li->direction = AL_START_HEAD; //迭代方向置为AL_START_HEAD，即从表头向表尾遍历
}
🏆 listRewindTail函数源码
💚 迭代器重新指向表尾💚
/* 功能：迭代器重新指向表头
* @param iter:链表
* @param li:迭代器
*/
void listRewindTail(list *list, listIter *li) {
li->next = list->tail;
li->direction = AL_START_TAIL; //迭代方向置为AL_START_TAIL，即从表尾向表头遍历
}
🏆 listNext函数源码
💚 返回迭代器的下一个元素💚
/* 功能：返回迭代器的下一个元素
* @param iter:链表
*/
listNode *listNext(listIter *iter)
{
listNode *current = iter->next;
if (current != NULL) {
if (iter->direction == AL_START_HEAD) //如果迭代方为AL_START_HEAD，即从表头向表尾遍历
iter->next = current->next; //保存指针的下一个节点
else
iter->next = current->prev;
}
return current;
}
为什么要保存指针的下一个节点那？
因为，指针的下一个节点没被保存，当前节点被删除后，就会找不到下一个节点，导致节点丢失，程序异常。
🏆 listDup函数源码
💚 复制一个链表💚
/* 功能：复制一个链表
* @param orig:原链表
*/
list *listDup(list *orig)
{
list *copy;
listIter *iter;
listNode *node;
if ((copy = listCreate()) == NULL)//创建空链表，失败则返回NULL
return NULL;
copy->dup = orig->dup;
copy->free = orig->free;
copy->match = orig->match;
iter = listGetIterator(orig, AL_START_HEAD); //获取一个迭代器
while((node = listNext(iter)) != NULL) { //当下一个元素不为空，则遍历执行复制操作
void *value;
if (copy->dup) {//如果定义了dup函数，则用dup函数进行拷贝
value = copy->dup(node->value);
if (value == NULL) {//复制结果为NULL,复制失败，则释放对应资源
listRelease(copy); //释放copy链表空间
listReleaseIterator(iter); //释放迭代器空间
return NULL; //复制失败，返回NUL
}
} else //如果没有定义dup函数，则直接将节点值进行赋值
value = node->value;
if (listAddNodeTail(copy, value) == NULL) {//将value插入到链表的尾部，如果失败，则释放对应资源
listRelease(copy);
listReleaseIterator(iter);
return NULL; //复制失败，返回NULL
}
}
listReleaseIterator(iter); //保障没有找到节点时，也能正确释放迭代器空间
return copy; //返回副本
}
注意，每次返回退出之前都要进行内存释放，避免内存泄漏。
🏆 listSearchKey函数源码
💚 查找链表中包含指定值的节点 💚
/* 功能：查找链表中包含指定值的节点
* @param list:原链表
* @param key:查找值
*/
listNode *listSearchKey(list *list, void *key)
{
listIter *iter;
listNode *node;
iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
if (list->match) {{//如果定义了match函数，则用match函数进行判断
if (list->match(node->value, key)) {
listReleaseIterator(iter);
return node; //返回找到的节点
}
} else { //如果没有定义了match函数，则用直接进行相等判断
if (key == node->value) {
listReleaseIterator(iter);
return node;//返回找到的节点
}
}
}
listReleaseIterator(iter); //保障没有找到节点时，也能正确释放迭代器空间
return NULL;//没找到，则返回NULL
}
🏆 listIndex函数源码
💚 返回链表中指定索引的节点 💚
/* 功能：返回链表中指定索引的节点
* @param list:原链表
* @param index:索引
*/
listNode *listIndex(list *list, PORT_LONG index) {
listNode *n;
if (index < 0) { //索引小于0，从尾部开始
index = (-index)-1; //变为正数，从尾部开始
n = list->tail; //从尾部开始查找
while(index-- && n) n = n->prev; //更新前置节点
} else {
n = list->head; //从头部开始查找
while(index-- && n) n = n->next; //更新后置节点
}
return n;
}
🏆 listRotate函数源码
💚 将链表的表尾节点弹出，然后将弹出的节点插入到表头，成为新的表头节点 💚
/* 功能：将链表的表尾节点弹出，然后将弹出的节点插入到表头，成为新的表头节点
* @param list:链表
*/
void listRotate(list *list) {
listNode *tail = list->tail;//表尾节点
if (listLength(list) <= 1) return;//链表只有一个节点或没有节点，ze
/* 更新表尾节点 */
list->tail = tail->prev;
list->tail->next = NULL;
/* 移动到表头 */
list->head->prev = tail;
tail->prev = NULL;
tail->next = list->head;
list->head = tail;
}
💖 redis链表特点
🍀 双端：链表节点具有前置指针和后置指针。
🍀 无环：表头的前置指针和表尾的后置指针都指向NULL，不构成环路，对链表的访问以NULL为终点。
🍀 链表长度计数，使用含有len属性的list结构，对链表长度进行计算和保存。
🍀 多态：节点使用void *类型保存节点值，所以，可保保存各种不同类型的值。
🍀 灵活：可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数。
💖 总结
redis链表实现还是不复杂的，希望继续努力，通过源码阅读发现自己知识盲点，提升知识储备，构建自己的知识体系。加油！
参考：
《Redis设计与实现》 《Redis学习之list底层链表源码分析》
