文中引用的源码，Redis3.2之前引用的是Redis3.0，Redis3.2及其之后引用的是Redis5.0
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
应用
列表键（值为列表的键，值的底层数据结构之一为链表）
发布和订阅功能
慢查询功能
监视器等功能
链表节点
结构体定义如下：
【src/adlist.h Redis3.2同Redis5.0】
/*
* 双端链表节点
*/
typedef struct listNode {
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
多个listNode组成双端链表：
redis中使用list结构体将listNode进行组装成更加方便地操作链表的结构体：
【src/adlist.h Redis3.2同Redis5.0】
/*
* 双端链表结构
*/
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;
由list结构和listNode结构组成的链表：
Redis实现的链表的特点：
- 双端：链表节点带有prev和next指针，对某个节点的前置节点和后置节点的访问时间复杂度为O(1)
- 无环：表头节点的prev和表尾节点的next值为NULL，对链表的访问以NULL结尾
- 链表带有指向表头节点和表尾节点的指针head和tail
- 带链表长度计数器len，获取链表长度的时间复杂度为O(1)
- 多态：链表节点使用void * 指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所有链表可以用于保存工作不同类型的值
部分源码解析
创建一个空的新链表
【src/adlist.c Redis5.0】
/*
* 创建一个新的链表
* 创建成功返回链表，失败返回 NULL 。
* T = O(1)
*/
list *listCreate(void)
{
struct list *list;
// 分配内存
if ((list = zmalloc(sizeof(*list))) == NULL)
return NULL;
// 初始化属性
list->head = list->tail = NULL;
list->len = 0;
list->dup = NULL;
list->free = NULL;
list->match = NULL;
return list;
}
将一个包含有给定值指针 value 的新节点添加到链表的表尾
【src/adlist.c Redis5.0】
/*
* 将一个包含有给定值指针 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;
}
通过上述两段源码，我们就清楚了当我们在redis客户端执行lpush language redis时底层做了什么操作。