List 定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 链表节点
typedef struct listNode {
struct listNode *prev, *next; // 前驱,后继节点
void *value; // void* 不对节点值做类型假设
} listNode;

// 无环双向链表
typedef struct list {
listNode *head, *tail; // 头尾节点

// 值复制、值释放、值比较,3 个节点值操作需由调用方实现并设置
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *value);

unsigned long len; // 节点个数,即链表长度
} list;

特点:

  • 多态:节点值类型为void*可存储任意类型值,同理节点值的复制、比较、内存释放需调用方自定义
  • 高频操作O(1)复杂度:空间换时间,动态维护len,head,tail,读取链表长度、头尾节点都非常快速

List API

注意:由于需额外维护链表元信息,操作时的 corner case 较多,比如要操作节点为空、为头尾节点等,需做好检查;修改指针的指向,最好先画图,逐个节点有序修改

1. 增删节点

插入新节点:在 head 前插入即 prepend,在 tail 后插入即 append:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list *listAddNodeHead(list *list, void *value) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
// 1. 空链表
list->head = list->tail = node; // 新 node 同时作为 head 和 tail
node->prev = node->next = NULL;
} else {
// 2. 插入 head 之前
node->prev = NULL; // 逐个节点修改指针指向
node->next = list->head;
list->head->prev = node;
list->head = node; // 替换新节点
}
list->len++; // 增删节点动态维护 list->len
return list;
}

list *listAddNodeTail(list *list, void *value); // 同理

在指定节点之前或之后插入:先更新 new_node 指向,再更新前后节点指针。示意图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;

// 1,2: 更新 new_node 指向
if (after) {
node->prev = old_node;
node->next = old_node->next;
if (list->tail == old_node) // 检查 tail 节点是否需更新
list->tail = node;
} else {
node->next = old_node;
node->prev = old_node->prev;
if (list->head == old_node) // 同理
list->head = node;
}
// 3,4: 更新 old_node 指向
if (node->prev != NULL)
node->prev->next = node;
if (node->next != NULL)
node->next->prev = node;
list->len++;
return list;
}

删除旧节点:断开前后节点的对应指针,释放节点内存。示意图:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void listDelNode(list *list, listNode *node) {
// 1. 更新 prev 的 next 指向
if (node->prev)
node->prev->next = node->next;
else // 删除头结点
list->head = node->next;
// 2. 更新 next 的 prev 指向
if (node->next)
node->next->prev = node->prev;
else // 删除尾节点
list->tail = node->prev;
if (list->free) list->free(node->value);
zfree(node);
list->len--;
}

2. 迭代器

链表的搜索和复制都需要遍历,故将遍历操作抽离到listIter并搭配对应 API 来实现;迭代器定义:

1
2
3
4
5
6
typedef struct listIter {
listNode *next; // 下一个迭代返回的节点
int direction;
} listIter;
#define AL_START_HEAD 0 // 正向遍历
#define AL_START_TAIL 1 // 反向

迭代伪代码:

1
2
3
iter = listGetIterator(list, direction);
while ((node = listNext(iter)) != NULL)
handleNode(listNodeValue(node));

迭代器的生成与使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
listIter *listGetIterator(list *list, int direction) {
listIter *iter;
if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
if (direction == AL_START_HEAD)
iter->next = list->head; // 类似哑节点,迭代器本身不存节点数据,仅指示迭代方向
else
iter->next = list->tail;
iter->direction = direction;
return iter;
}

// 返回下一个待处理节点
listNode *listNext(listIter *iter) {
listNode *current = iter->next;
if (current != NULL) {
if (iter->direction == AL_START_HEAD)
iter->next = current->next;
else
iter->next = current->prev; // 向前遍历
}
return current;
}

3. 搜索与复制

使用迭代器遍历链表,配合用户指定的cmp, dup函数来做搜索比较、节点复制等操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
listNode *listSearchKey(list *list, void *key) {
listIter *iter;
listNode *node;

iter = listGetIterator(list, AL_START_HEAD);
while((node = listNext(iter)) != NULL) {
if (list->match) {
if (list->match(node->value, key)) {
listReleaseIterator(iter);
return node;
}
} else {
if (key == node->value) { // 用户未指定 cmp 函数则直接比较指针值
listReleaseIterator(iter);
return node;
}
}
}
listReleaseIterator(iter);
return NULL;
}

list *listDup(list *orig); // 类似

总结

Redis 的 List 相比普通的双向链表,主要有 3 个优势:一是未对节点值做类型假设,将三个节点操作以函数指针的形式开放给用户自定义;二是节点增删都动态维护len元信息,使得O(1)读取链表长度;三是实现了迭代器,规范了迭代模式