Doubly Linked List

1 minute read

链表是线性表的一种实现，在 Redis 中也是列表类型的底层实现之一。C 标准库没有内建的链表类型，所以 Redis 自己实现了一个泛型双向链表。由于链表的操作和结构有广泛的认识基础，本文仅做简单说明。

概述

  • adlist.h
  • adlist.c

Redis 中的链表是一个带头节点的双向链表，同时头节点还有指向尾部的指针域。结构如图示：

adlist

同时 Redis 中还定义了一个迭代器，指向链表中的一个节点并且标识出来迭代方向。定义如下：

1
2
3
4
5
6
7
8
9
10

//adlist.h:42
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;

//adlist.h:92
/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1

有结构可知，除了双向链表固有的特点之外，Redis 的双向链表还有以下特点：

  • 有固定的头节点；
  • 头节点保存链表的长度；
  • 无环且头节点有指向头节点和尾节点的域；
  • 提供了三个函数指针，用于链表节点的复制、释放和比较，由调用方根据存储的数据类型自行实现。

操作

内存管理

Reids 链表主要依赖底层内存管理实现，具体分析参见章节Redis 内存管理。比较特别的是，链表头存储了节点内存释放的函数指针，需要调用方自行实现。

宏函数

链表操作的宏函数主要以取结构中某些字段为主，逻辑简单，仅贴上源码，顾名思义即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//adlist.h:56
/* 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)

链表的 CRUD

创建adlist.c:41#listCreate(void)->list *

创建链表实质上是初始化一个空的头节点，申请头节点内存并将所有域置为NULL，长度设置为0。特别的，内存申请失败后返回的头节点地址为NULL。

复制adlist.c:250#listDup(list *)->list *

复制链表依赖链表创建和链表迭代器。特别的，链表节点的复制依赖头节点的dup域，可以实现多态下的节点值深拷贝。

节点插入

链表增加节点分为头插、尾插和给定节点前后插入值，具体逻辑不赘述，仅列出实现的函数。

  • adlist.c:88#listAddNodeHead(list *, void *)->list *
  • adlist.c:114#listAddNodeTail(list *, void *)->list *
  • adlist.c:134#listInsertNode(list *, listNode *, void *, int)->list *
    • 本函数做简单额外说明。形参的最后一个用作 bool 值，表示插入方向。

上述函数均以返回值作为链表头节点，原头节点不应有任何读写操作。如果返回值为NULL，则表明内存操作返回为空，应该以操作失败处理。

节点的删除与内容清空

逻辑简单不赘述，仅列出函数。特别的，如果头节点free域有值，则可以实现调用方自行析构节点。

  • adlist.c:167#listDelNode(list *, listNode *)
  • adlist.c:56#listEmpty(list *)

遍历

Redis 的双向链表提供了迭代器形式的遍历，支持从头节点或尾节点的双向遍历。

链表的释放adlist.c:76#listRelease(list *)

先清空链表（即释放所有节点），再释放头节点。

API汇总

注：调用返回值类型为list的函数后，应使用返回值作为新链表使用，原链表不应再有任何读写操作。

注2：复杂度中的问题规模 N 表示链表的节点数量

函数声明 源码位置 功能简要说明 时间复杂度
list *listCreate(void) adlist.c:41 初始化空的头节点 O(1)
void listRelease(list *list) adlist.c:76 释放链表所有节点（包括头节点） O(N)
void listEmpty(list *list) adlist.c:56 释放链表所有节点（头节点除外） O(N)
list *listAddNodeHead(list *list, void *value) adlist.c:88 头插节点 O(1)
list *listAddNodeTail(list *list, void *value) adlist.c:114 尾插节点 O(1)
list *listInsertNode(list *list, listNode *old_node, void *value, int after) adlist.c:134 指定节点（未校验节点是否属于链表）前或后插入 O(1)
void listDelNode(list *list, listNode *node) adlist.c:167 删除指定节点（未校验节点是否属于链表） O(1)
listIter *listGetIterator(list *list, int direction) adlist.c:186 指定方向获取链表迭代器 O(1)
listNode *listNext(listIter *iter) adlist.c:229 获取迭代器下一个指向的节点（空值表示迭代结束） O(1)
void listReleaseIterator(listIter *iter) adlist.c:200 释放迭代器 O(1)
list *listDup(list *orig) adlist.c:250 复制链表 O(N)
listNode *listSearchKey(list *list, void *key) adlist.c:290 列表中查找指定值（值比较可以由调用方自定义）的节点，未找到时返回空 O(N)
listNode *listIndex(list *list, long index) adlist.c:315 指定索引（起点为0，负数表示从尾节点向前）查找链表节点，未找到时返回空 O(N)
void listRewind(list *list, listIter *li) adlist.c:205 初始化正向迭代器 O(1)
void listRewindTail(list *list, listIter *li) adlist.c:210 初始化逆向迭代器 O(1)
void listRotateTailToHead(list *list) adlist.c:330 尾节点变头节点 O(1)
void listRotateHeadToTail(list *list) adlist.c:345 头节点变尾节点 O(1)
void listJoin(list *l, list *o) adlist.c:361 链表追加（操作后 o 依然是有效的头节点，只是节点为空长度为0） O(1)

参考

Updated: