由于Redis使用的C语言并没有内置这种数据结构，所以Redis构建了自己的链表实现。
1. 定义
每个链表节点使用一个adlist.h/listNode结构来表示：
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
多个listNode可以通过prev和next指针组成双断了链表，如图所示。
image
需要有一个结构，来持有这些链节点。这里使用adlist.h/list。
/*
* 双端链表结构
*/
typedef struct list {
// 表头节点
listNode *head;
// 表尾节点
listNode *tail;
// 节点值复制函数
void *(*dup)(void *ptr);
// 节点值释放函数
void (*free)(void *ptr);
// 节点值对比函数
int (*match)(void *ptr, void *key);
// 链表所包含的节点数量
unsigned long len;
} list;
各参数含义：
- dup函数用于复制链表节点所保存的值;
- free函数用于释放链表节点所保存的值;
- match函数则用于对比链表节点所保存的值和另一个输入值是否相等。
2. 特性
Redis的链表实现的特性可以总结如下：
- 双端∶链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
- 无环∶表头节点的prev指针和表尾节点的 next指针都指向 NULL，对链表的访问以 NULL为终点。
- 带表头指针和表尾指针∶通过1list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)。
- 带链表长度计数器∶ 程序使用list 结构的1en属性来对list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)。
- 多态∶链表节点使用void*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。
3. 源码
这里只分析添加和删除的逻辑。
3.1 listAddNodeHead 表头添加节点
看源码之前，我们先想一下，如何在双端链表中的表头添加一个节点，首先要分两种情况，第一个是空链表添加节点，第二个是在头结点前插入。结合双端链表的特性，可以总结为如下操作步骤：
如果是空链表的话：
- 将list的head和tail指向要插入的node;
- 将node的prev和next指向NULL
如果要在头结点前插入：
- 将当前node的prev指向NULL,next指向head；
- 将list中head的prev指向当前node；
- 将list中的head指向node
相关源码
/*
* 将一个包含有给定值指针 value 的新节点添加到链表的表头
*
* 如果为新节点分配内存出错，那么不执行任何动作，仅返回 NULL
*
* 如果执行成功，返回传入的链表指针
*
* T = O(1)
*/
list *listAddNodeHead(list *list, void *value)
{
listNode *node;
// 为节点分配内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 保存值指针
node->value = value;
// 添加节点到空链表
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
// 添加节点到非空链表
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
// 更新链表节点数
list->len++;
return list;
}
同理，可以自行分析表尾添加节点的过程。
3.2 listAddNodeTail 表尾添加节点
/*
* 将一个包含有给定值指针 value 的新节点添加到链表的表尾
*
* 如果为新节点分配内存出错，那么不执行任何动作，仅返回 NULL
*
* 如果执行成功，返回传入的链表指针
*
* T = O(1)
*/
list *listAddNodeTail(list *list, void *value)
{
listNode *node;
// 为新节点分配内存
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 保存值指针
node->value = value;
// 目标链表为空
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
// 目标链表非空
} else {
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
// 更新链表节点数
list->len++;
return list;
}
3.3 listInsertNode 在指定节点之前或之后插入节点
这个操作稍微有一点复杂，需要分别考虑在制定节点之前插入，或者指定节点之后插入，还要判断指定节点属于头结点或尾结点。
这里假设指定节点为old_node，当前节点为node，先分析在指定节点之后添加新节点的情况:
- 将node->prev指向old_node;
- 将node->next指向old_node->next;
- 如果old_node是尾结点，将list->tail指向node;
- 再将node前边节点的next指向node，后边节点的prev指向node，node->prev->next指向node，node->next->prev指向node
- 更新链表节点数
同理，可分析在当前节点之前添加新节点的情况
/*
* 创建一个包含值 value 的新节点，并将它插入到 old_node 的之前或之后
*
* 如果 after 为 0 ，将新节点插入到 old_node 之前。
* 如果 after 为 1 ，将新节点插入到 old_node 之后。
*
* T = O(1)
*/
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
// 创建新节点
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
// 保存值
node->value = value;
// 将新节点添加到给定节点之后
if (after) {
node->prev = old_node;
node->next = old_node->next;
// 给定节点是原表尾节点
if (list->tail == old_node) {
list->tail = node;
}
// 将新节点添加到给定节点之前
} else {
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++;
return list;
}
3.4 listDelNode 从链表中删除给定节点node
删除可以分为三种情况，删除头结点、删除中间节点以及删除尾结点。这里分析最复杂的删除中间节点的情况，其他两种按这个思路分析即可。
假定当前节点为node:
- 将node的上一个节点的next指向node.next;
- 将node的下一个节点的prev指向node.prev
/*
* 从链表 list 中删除给定节点 node
*
* 对节点私有值(private value of the node)的释放工作由调用者进行。
*
* T = O(1)
*/
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--;
}
网友评论