Redis源码学习基本数据结构之链表

介绍

双端链表作为一种通用的数据结构，在 Redis 内部使用得非常多，它既是 Redis 列表结构的底层实现之一，还被大量 Redis 模块所使用，用于构建 Redis 的其他功能。关联源码adlist.h/adlist.c

结构

//链表节点
typedef struct listNode {
    struct listNode *prev;//上一个节点
    struct listNode *next;//下一个节点
    void *value;//值
} listNode;

//链表的迭代器
typedef struct listIter {
    listNode *next;//下一个节点
    int direction;//迭代方向(正向迭代还是反向迭代)
} listIter;

//链表
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;

宏定义的函数

#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)

函数

list *listCreate(void);//创建一个双向链表
void listRelease(list *list);//释放双向链表内存
void listEmpty(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);//old_node之前或者之后插入value元素
void listDelNode(list *list, listNode *node);//删除一个节点
listIter *listGetIterator(list *list, int direction);//返回list的迭代器
listNode *listNext(listIter *iter);//list下一个节点
void listReleaseIterator(listIter *iter);//释放迭代器内存
list *listDup(list *orig);//复制链表
listNode *listSearchKey(list *list, void *key);//寻找key与链表中数据一样的或者想匹配的节点
listNode *listIndex(list *list, long index);//找到第index个节点 0表示head  -1表示tail
void listRewind(list *list, listIter *li);//创建一个从head开始的正向链表迭代器
void listRewindTail(list *list, listIter *li);//创建一个从tail开始的正向链表迭代器
void listRotate(list *list);//将尾部节点移除插入到头部
void listJoin(list *l, list *o);//将o拼接到o上去

链表及其节点的性能特性

• 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 O(1) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行。
• 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 O(1) 。
• 链表带有记录节点数量的属性，所以可以在 O(1) 复杂度内返回链表的节点数量（长度）。

参考：

• 《Redis设计与实现》
• https://github.com/antirez/redis