对比分析 Redis 链表与其他链表结构
2023-06-065.7k 阅读
Redis 链表概述
Redis 链表结构基础
Redis 链表是其内部实现的一种数据结构，用于存储一系列节点。在 Redis 中，链表结构主要由链表头（list）、链表节点（listNode）和链表迭代器（listIter）组成。链表节点结构 listNode 定义如下：
typedef struct listNode {
struct listNode *prev;
struct listNode *next;
void *value;
} listNode;
从上述代码可以看出，listNode 结构体包含三个成员。prev 指针指向前一个节点，next 指针指向后一个节点，value 指针则用于存储节点的值，这使得 Redis 链表成为一个双向链表。这种双向链表结构允许在 O(1) 的时间复杂度内从链表的任意一端访问相邻节点。
链表头结构 list 定义如下：
typedef struct list {
listNode *head;
listNode *tail;
unsigned long len;
void *(*dup)(void *ptr);
void (*free)(void *ptr);
int (*match)(void *ptr, void *key);
} list;
list 结构体包含链表头节点指针 head、链表尾节点指针 tail、链表长度 len，以及三个函数指针 dup、free 和 match。dup 函数用于复制节点的值，free 函数用于释放节点的值，match 函数用于比较节点的值和给定的键。这些函数指针使得 Redis 链表具有高度的灵活性，可以适应不同类型数据的存储需求。
Redis 链表的主要操作
- 插入操作：Redis 链表支持在链表头和链表尾插入新节点。以在链表头插入节点为例，其实现代码如下：
list *listAddNodeHead(list *list, void *value) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
}
list->len++;
return list;
}
在链表头插入节点时，首先为新节点分配内存，然后根据链表当前是否为空进行不同的处理。如果链表为空，则新节点既是头节点也是尾节点；如果链表不为空，则将新节点插入到链表头，并更新相关指针。
- 删除操作：删除节点的操作同样高效，其实现代码如下：
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--;
}
删除节点时，首先调整相邻节点的指针，使其绕过待删除节点。然后，如果定义了 free 函数，则释放节点的值，最后释放节点本身，并更新链表长度。
- 遍历操作：Redis 提供了链表迭代器
listIter来遍历链表。listIter结构体定义如下：
typedef struct listIter {
listNode *next;
int direction;
} listIter;
next 指针指向下一个要遍历的节点，direction 用于指定遍历方向，取值为 AL_START_HEAD（从链表头开始遍历）或 AL_START_TAIL（从链表尾开始遍历）。遍历链表的示例代码如下：
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;
}
通过 listGetIterator 函数获取迭代器，并使用 listNext 函数逐一遍历链表节点。
与传统单链表对比
结构差异
- 指针指向：传统单链表的节点只包含一个指向下一个节点的指针，例如在 C 语言中，其节点结构可能定义为：
typedef struct SingleListNode {
struct SingleListNode *next;
void *value;
} SingleListNode;
而 Redis 链表的节点包含两个指针，一个指向前一个节点，一个指向后一个节点，形成双向链表结构。这种结构上的差异使得 Redis 链表在遍历方向上更加灵活，可以从链表头或链表尾开始遍历，而传统单链表通常只能从链表头开始单向遍历。
- 链表头结构：传统单链表的链表头可能只包含一个指向第一个节点的指针，如：
typedef struct SingleList {
SingleListNode *head;
} SingleList;
而 Redis 链表的链表头结构 list 不仅包含头节点和尾节点的指针，还包含链表长度以及用于数据处理的函数指针。这使得 Redis 链表在管理和操作数据时更加方便，例如可以直接获取链表长度，并且可以根据不同的数据类型自定义数据的复制、释放和比较操作。
操作性能对比
- 插入操作：
- 传统单链表：在链表头插入新节点的时间复杂度为 O(1)，因为只需修改头指针。但在链表尾插入新节点时，需要遍历到链表尾才能完成插入操作，时间复杂度为 O(n)，其中 n 为链表长度。
- Redis 链表：无论是在链表头还是链表尾插入新节点，时间复杂度均为 O(1)。这是因为 Redis 链表的双向链表结构使得可以直接获取链表头和链表尾节点，无需遍历链表。例如在链表尾插入节点的代码如下：
list *listAddNodeTail(list *list, void *value) {
listNode *node;
if ((node = zmalloc(sizeof(*node))) == NULL)
return NULL;
node->value = value;
if (list->len == 0) {
list->head = list->tail = node;
node->prev = node->next = NULL;
} else {
node->prev = list->tail;
node->next = NULL;
list->tail->next = node;
list->tail = node;
}
list->len++;
return list;
}
-
删除操作：
- 传统单链表：删除节点时，如果已知要删除节点的前驱节点，时间复杂度为 O(1)，只需修改前驱节点的
next指针。但如果不知道前驱节点，需要遍历链表找到前驱节点，时间复杂度为 O(n)。另外，删除链表尾节点时，也需要遍历链表找到尾节点的前驱节点，时间复杂度为 O(n)。 - Redis 链表：删除任意节点的时间复杂度均为 O(1)。因为 Redis 链表的双向链表结构使得可以直接获取节点的前驱和后继节点，通过调整指针即可完成删除操作，如前文
listDelNode函数所示。
- 传统单链表：删除节点时，如果已知要删除节点的前驱节点，时间复杂度为 O(1)，只需修改前驱节点的
-
遍历操作：
- 传统单链表：只能从链表头开始单向遍历，时间复杂度为 O(n)。如果需要反向遍历，则需要额外的处理，例如在遍历过程中记录节点顺序，然后反向输出。
- Redis 链表：可以从链表头或链表尾开始遍历，时间复杂度同样为 O(n)。通过链表迭代器
listIter，可以方便地实现正向或反向遍历，如前文listGetIterator和listNext函数所示。
与双向循环链表对比
结构特点对比
- 循环特性：双向循环链表的节点结构与 Redis 链表类似，也是双向的，但双向循环链表的头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成一个循环结构。其节点结构可能定义为：
typedef struct DoublyCircularListNode {
struct DoublyCircularListNode *prev;
struct DoublyCircularListNode *next;
void *value;
} DoublyCircularListNode;
而 Redis 链表是普通的双向链表，头节点的前驱指针和尾节点的后继指针均为 NULL。
- 链表头结构：双向循环链表的链表头可能只包含一个指向头节点的指针，因为通过头节点可以访问到链表的任意节点。例如：
typedef struct DoublyCircularList {
DoublyCircularListNode *head;
} DoublyCircularList;
Redis 链表的链表头结构 list 除了包含头节点和尾节点指针外，还包含链表长度和数据处理函数指针，这使得 Redis 链表在数据管理方面更加便捷。
操作差异分析
-
插入操作：
- 双向循环链表：在链表头插入新节点时，需要调整头节点的前驱指针、新节点的前驱和后继指针以及尾节点的后继指针（因为是循环链表），时间复杂度为 O(1)。在链表尾插入新节点同样需要调整多个指针，时间复杂度也为 O(1)。
- Redis 链表：在链表头和链表尾插入新节点的操作与双向循环链表类似，时间复杂度均为 O(1)。但 Redis 链表的插入操作相对简单，因为不需要处理循环结构的指针调整。例如在 Redis 链表头插入节点时，只需调整新节点与头节点的指针关系，而双向循环链表还需额外处理尾节点与新节点的关系。
-
删除操作：
- 双向循环链表：删除节点时，需要根据节点位置调整前驱和后继节点的指针，并且要注意循环结构的维护。如果删除的是头节点，还需要更新链表头指针。时间复杂度为 O(1)，但指针调整相对复杂。
- Redis 链表：删除节点时，同样调整前驱和后继节点的指针即可，时间复杂度为 O(1)。由于 Redis 链表不是循环结构，指针调整相对简洁，例如删除头节点时，只需将头指针指向下一个节点，而双向循环链表还需处理尾节点与新头节点的关系。
-
遍历操作：
- 双向循环链表：可以从任意节点开始遍历，因为链表是循环的。遍历到链表尾后会回到链表头继续遍历，时间复杂度为 O(n)。但在遍历结束条件判断上需要注意，通常不能以节点指针是否为 NULL 作为结束条件，而是需要设置一个遍历次数计数器或者判断是否回到起始节点。
- Redis 链表：可以从链表头或链表尾开始遍历，遍历到链表尾（或头）后结束，时间复杂度为 O(n)。遍历结束条件简单，当头指针（或尾指针）为 NULL 时结束遍历。例如使用 Redis 链表迭代器遍历链表的代码如下：
listIter *iter = listGetIterator(list, AL_START_HEAD);
listNode *node;
while ((node = listNext(iter)) != NULL) {
// 处理节点数据
}
listReleaseIterator(iter);
与跳跃链表对比
结构本质区别
- 多层结构：跳跃链表是一种多层结构的链表，每个节点可能存在于多个层次中。高层次的节点是低层次节点的子集，通过这种结构可以快速定位到目标节点。例如，一个简单的跳跃链表节点结构可能定义为：
typedef struct SkipListNode {
struct SkipListNode *forward[];
void *value;
int score;
} SkipListNode;
其中 forward 数组用于存储不同层次的后继节点指针，score 用于节点排序。
而 Redis 链表是普通的双向链表，只有一层结构，节点之间通过 prev 和 next 指针连接。
- 随机化层次：跳跃链表的节点层次是通过随机化方式确定的，通常根据一定的概率（如 50% 的概率将节点提升到上一层）来决定节点是否出现在更高层次。这种随机化的层次结构使得跳跃链表在查找操作上具有近似于平衡二叉树的性能。 Redis 链表没有这种随机化层次结构，节点之间的连接关系是固定的双向连接。
操作性能比较
- 查找操作：
- 跳跃链表：查找操作的平均时间复杂度为 O(log n)，因为可以通过高层次的节点快速跳过大量节点，定位到目标节点所在的范围，然后在低层次中精确查找。例如，假设有一个包含 n 个节点的跳跃链表，最高层次有 k 个节点，通过高层次节点可以快速缩小查找范围，使得查找效率大大提高。
- Redis 链表：查找操作的时间复杂度为 O(n)，因为需要从链表头或链表尾开始逐个节点比较，直到找到目标节点。例如，在 Redis 链表中查找值为
target的节点，代码可能如下：
listNode *node = list->head;
while (node != NULL) {
if (list->match(node->value, target)) {
return node;
}
node = node->next;
}
return NULL;
-
插入操作：
- 跳跃链表：插入操作首先需要查找插入位置，平均时间复杂度为 O(log n)，然后插入节点并调整层次结构，平均时间复杂度也为 O(log n)。因此，总体插入操作的平均时间复杂度为 O(log n)。插入新节点时，需要根据随机化规则确定新节点的层次，并调整相应层次的指针。
- Redis 链表：插入操作在链表头或链表尾的时间复杂度为 O(1)，在指定位置插入时，需要先查找指定位置，时间复杂度为 O(n)，然后进行插入操作，时间复杂度为 O(1)。因此，在指定位置插入的总体时间复杂度为 O(n)。
-
删除操作：
- 跳跃链表：删除操作首先需要查找要删除的节点，平均时间复杂度为 O(log n)，然后删除节点并调整层次结构，平均时间复杂度也为 O(log n)。因此，总体删除操作的平均时间复杂度为 O(log n)。删除节点时，需要从各个层次中移除该节点，并调整相邻节点的指针。
- Redis 链表：删除操作的时间复杂度为 O(1)，因为可以直接通过指针调整移除节点，如前文
listDelNode函数所示。但如果不知道要删除节点的指针，需要先查找节点，时间复杂度为 O(n)。
与哈希链表对比
数据组织方式差异
- 哈希映射：哈希链表（通常指哈希表中解决冲突的链表结构）是基于哈希函数将键映射到特定的桶（bucket）中，每个桶中可能包含一个链表来存储冲突的键值对。例如，在 C 语言中，一个简单的哈希链表节点结构可能定义为：
typedef struct HashListNode {
char *key;
void *value;
struct HashListNode *next;
} HashListNode;
哈希表通过计算键的哈希值来确定键值对存储的桶位置。 Redis 链表则是按照插入顺序或特定的逻辑顺序存储节点，节点之间通过双向指针连接，不依赖哈希函数进行数据定位。
- 键值对存储：哈希链表主要用于存储键值对数据，并且通过哈希函数快速定位键对应的节点。而 Redis 链表虽然也可以存储键值对（通过将键值对封装在节点的
value中），但它更侧重于按顺序存储一系列数据，例如在 Redis 的列表（list）数据结构中，用于存储一系列字符串等数据。
应用场景及性能对比
-
查找操作：
- 哈希链表：在理想情况下，哈希链表的查找操作平均时间复杂度为 O(1)，因为通过哈希函数可以直接定位到键所在的桶，然后在桶内的链表中查找。但如果哈希冲突严重，链表长度增加，查找时间复杂度会退化为 O(n)，其中 n 为链表长度。
- Redis 链表：查找操作的时间复杂度为 O(n)，需要从链表头或链表尾开始逐个节点比较，直到找到目标节点，如前文查找代码所示。
-
插入操作：
- 哈希链表：插入操作首先计算键的哈希值确定桶位置，然后在桶内链表头插入新节点，平均时间复杂度为 O(1)。但如果哈希冲突严重，链表长度增加，插入操作的时间复杂度会受到影响。
- Redis 链表：在链表头或链表尾插入新节点的时间复杂度为 O(1)，在指定位置插入时，需要先查找指定位置，时间复杂度为 O(n)，然后进行插入操作，时间复杂度为 O(1)。因此，在指定位置插入的总体时间复杂度为 O(n)。
-
删除操作：
- 哈希链表：删除操作首先计算键的哈希值确定桶位置，然后在桶内链表中查找并删除节点，平均时间复杂度为 O(1)。但同样在哈希冲突严重时，时间复杂度会增加。
- Redis 链表：删除操作的时间复杂度为 O(1)，前提是已知要删除节点的指针。如果不知道要删除节点的指针，需要先查找节点，时间复杂度为 O(n)。
在应用场景方面，哈希链表适用于需要快速查找键值对的场景，如数据库索引等。而 Redis 链表适用于需要按顺序存储和操作数据的场景，如 Redis 的列表数据结构，用于实现队列、栈等功能。
总结 Redis 链表的独特优势
通过与传统单链表、双向循环链表、跳跃链表和哈希链表的对比分析，可以看出 Redis 链表具有以下独特优势：
- 双向链表结构：使得在链表头和链表尾插入、删除节点的操作都具有 O(1) 的时间复杂度，并且可以方便地从链表头或链表尾开始遍历，灵活性较高。
- 链表头结构设计：包含链表长度和数据处理函数指针，方便管理链表和处理不同类型的数据，提高了代码的复用性和可扩展性。
- 简单高效：相对于一些复杂的数据结构如跳跃链表，Redis 链表结构简单，实现和维护成本较低，适合在一些对结构复杂度要求不高，但对插入、删除和顺序遍历操作有一定性能要求的场景中使用，如 Redis 的列表数据结构实现。
在实际应用中，应根据具体的需求选择合适的数据结构。如果需要快速查找操作，哈希链表或跳跃链表可能更合适；如果需要按顺序存储和操作数据，并且对插入、删除操作性能有要求，Redis 链表则是一个不错的选择。