Redis原理再学习03：数据结构-链表 list

链表list介绍

1. 链表list简介

链表（linked list）是一种基础数据结构，是一种线性表，但是不会按照线性表的顺序存储数据，而是在每一个节点里存到下一个节点的指针。

链表插入节点时是 O(1) 复杂度，比线性表顺序表快。

链表访问节点或访问特殊节点时是 O(N) 复杂度时间，顺序表相应复杂度是 O(logn)和O(1)。

--- 维基百科-链表

2. 链表结构

• 单向链表
• 双向链表
• 循环链表
• 块状结构
• 其它扩展

下面看看最经常用到的 3 种链表。

单向链表：

双向链表：

循环链表：

说明：以上图片来自维基百科-链表

Redis中的链表

Redis3.0 中使用的链表结构是双向链表。看看它的结构定义，在文件 adlist.h 中。

1. 节点 Node 定义

// https://github.com/redis/redis/blob/3.0/src/adlist.h#L36
/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev; // 前置节点指针
    struct listNode *next; // 后置节点指针
    void *value;           // 节点的值
} listNode;

上面 listNode 可以组成一个链表结构，如下图：

上面的 listNode 也可以组成一个链表，但是操作起来不是很方便。为了更方便的操作定义了一个 list 的链表。

2. 链表 list 定义

// https://github.com/redis/redis/blob/3.0/src/adlist.h#L47
typedef struct list {
    listNode *head;  // 链表头部节点指针，指向第一个Node节点
    listNode *tail;  // 链表尾部节点指针，指向最后一个Node节点
    void *(*dup)(void *ptr); // 节点值复制函数
    void (*free)(void *ptr);  // 节点值释放函数
    int (*match)(void *ptr, void *key); // 节点值对比函数
    unsigned long len; // 链表的长度
} list;

一个链表 list 长度为 4 的结构示意图如下：

Redis 定义的双向链表的好处：

1. 获取某节点的前置节点和后置节点的复杂度为O(1)，因为链表带有 prev 和 next 指针。

2. 获取链表头节点和尾节点的复杂度为O(1)，因为链表带有表头指针 head 和表尾指针 tail。

3. 计算链表节点数量的复杂度为O(1)，因为有 len 属性。

4. 每个节点可以保存任意值，因为是 *void 定义值类型。

3. 操作链表list的API

把一些对list和listNode查询值和赋值封装成宏操作：

// https://github.com/redis/redis/blob/3.0/src/adlist.h#L56
/* Functions implemented as macros */
#define listLength(l) ((l)->len) // 获取节点数量
#define listFirst(l) ((l)->head) // 获取链表头部节点 
#define listLast(l) ((l)->tail)  // 获取链表尾部节点
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)

#define listSetDupMethod(l,m) ((l)->dup = (m))
#define listSetFreeMethod(l,m) ((l)->free = (m))
#define listSetMatchMethod(l,m) ((l)->match = (m))

#define listGetDupMethod(l) ((l)->dup)
#define listGetFree(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)

链表操作的函数原型：

// https://github.com/redis/redis/blob/3.0/src/adlist.h#L72
/* Prototypes */
list *listCreate(void); // 初始化链表
void listRelease(list *list); // 释放链表头和链表
list *listAddNodeHead(list *list, void *value); // 将值添加到链表的头部
list *listAddNodeTail(list *list, void *value); // 将值添加到链表的尾部
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotate(list *list);

listCreate 函数代码：

创建一个新的链表 list，给 list 各个成员赋值默认值。

// https://github.com/redis/redis/blob/3.0/src/adlist.c#L41

/* Create a new list. The created list can be freed with
 * AlFreeList(), but private value of every node need to be freed
 * by the user before to call AlFreeList().
 *
 * On error, NULL is returned. Otherwise the pointer to the new list. */
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;
}

listRelease 释放链表和链表中的节点操作：

// https://github.com/redis/redis/blob/3.0/src/adlist.c#L55
/* Free the whole list.
 *
 * This function can't fail. */
// 释放整个链表和链表中的节点
void listRelease(list *list)
{
    unsigned long len;
    listNode *current, *next;

    current = list->head; // 指向头指针
    // 遍历链表
    len = list->len;
    while(len--) {
        next = current->next;
        if (list->free) list->free(current->value);// 如果设置list节点释放函数，则释放调用函数节点值
        // 释放节点结构
        zfree(current);
        current = next;
    }
    // 释放链表
    zfree(list);
}

listInsertNode 插入 Node 节点的函数：

// https://github.com/redis/redis/blob/3.0/src/adlist.c#L126

// 创建一个带有值的新节点，插入到 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; // 给新节点赋值
    
    if (after) { // 将新节点添加到给定节点 old_node 之后
        node->prev = old_node;
        node->next = old_node->next;
        if (list->tail == old_node) { // 如果链表尾节点等于old_node节点时，那么就把list的尾节点更新为添加的node节点
            list->tail = node;
        }
    } else { // 将新节点添加到给定节点 old_node 之前
        node->next = old_node;
        node->prev = old_node->prev;
        if (list->head == old_node) {// 如果链表头节点等于old_node节点时，那么就把list的头节点更新为添加的node节点 
            list->head = node;
        }
    }
    if (node->prev != NULL) { // 更新给定节点的前置指针
        node->prev->next = node;
    }
    if (node->next != NULL) { // 更新给定节点的后置指针
        node->next->prev = node;
    }
    list->len++; // 更新链表节点数
    return list;
}

listDelNode 删除 node 节点的函数：

// https://github.com/redis/redis/blob/3.0/src/adlist.c#L159
/* Remove the specified node from the specified list.
 * It's up to the caller to free the private value of the node.
 *
 * This function can't fail. */
// 从链表list中删除指定节点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--; // 把链表长度减一
}

参考

• 《redis设计与实现》 作者：黄健宏

• redis.io

• github redis3.0-list

• github redis3.0-list