1. 链表定义

链表节点的定义为listNode：

typedef struct listNode {
    struct listNode *prev; // 前驱
    struct listNode *next; // 后驱
    void *value; // 值指针(它需要用list定义的dup/free/match函数来复制/释放/匹配)
} listNode;

为了方便操作，定义了list，表示一个列表：

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;

同样它实现了迭代器listIter，它可以双向迭代：

typedef struct listIter {
    listNode *next; // 对应方向的后驱节点
    int direction; // 前进方向(AL_START_HEAD: 向后; AL_START_TAIL: 向前)
} listIter;

从上面的这些定义里可以看出， Redis的链表：

双向：可向前/向后遍历
无环：head->prev == tail->next == NULL
多态
- 节点可存储任意的值，因为它用void *
- 节点值的操作函数（dup,free,match）可以有不同的实现，只需将实现赋值到对应的函数指针上

2. 链表操作

具体链表操作不再说明，API说明可参考:这里。

这里主要说明一下迭代器的实现，主要涉及3~4个函数：

void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
listNode *listNext(listIter *iter);

首先调用第一个/第二个函数创建迭代器，前者从头开始，后者从尾开始；

然后调用第三个函数迭代列表，注意要判空；

实例：

// ...
list* list = ...;
listNode* node = NULL;
listIter it;
// 从头向后遍历
listRewind(list, &it);
while((node = listNext(it)) != NULL) {
    // ...
}

源码阅读-Redis数据结构: 双向链表

1. 链表定义

2. 链表操作

CATALOG

FEATURED TAGS