上一篇文章我们学习了Redis的数据结构之简单动态字符串,这一篇我们接着来学习Redis中另外一个数据结构-链表。链表有很多种,首先,本文会首先回顾一下一些常见的链表,接着就是介绍Redis中的链表的结构。
数组是需要一块连续的内存空间来存储的,而链表值需要零散的内存碎片,数组的插入和删除的时间复杂度是0(n),查询的某个元素的时间复杂度是O(1)。而链表插入和删除的时间复杂度是O(1),查询某个节点的时间复杂度是O(n)通过指针相连即可。如下图所示:
在这里插入图片描述
单链表是最简单的链表,链表中的每一个内存块称之为“结点”,每个结点Node包含两个部分,数据域data和后继指针next。单链表的第一个结点称为头结点,头结点记录了链表的基地址。其next指针指向下一个结点,通过头结点可以遍历整个链表,最后一个结点称为尾结点,尾结点的next指针指向空地址NULL。更多关于单链表的知识可以参考第八篇:链表的学习:链表的头插法和尾插法以及HashMap中链表结点的插入方式
在这里插入图片描述
与单链表不同的是双向链表多了一个前驱指针prev。需要额外的空间存储前驱结点的地址,因此存储同样的数据,双端链表占用比单链表更多的空间,但是其优点是支持双向遍历。体现在如下两个方面:
在这里插入图片描述
循环链表与单链表和双链表的不同之处是其呈环状。单循环链表中其尾节点并非指向NULL而是指向头节点。双循环链表其头节点的前驱指针指向尾节点。尾节点的后继指针指向头节点。循环链表的优势在于链尾到链头,链头到链尾比较方便。适合处理具有环形结构的数据。
在这里插入图片描述
Redis链表使用的是双端无环链表。如下列表命令从左边添加元素:lpush lists 1 2 3
。就是通过链表左边设置了三个元素。
在这里插入图片描述
Redis使用一个listNode结构来表示链表的结点。
typedef struct listNode
{
// 前置节点
struct listNode *prev;
// 后置节点
struct listNode *next;
// 节点的值
void *value;
} listNode;
用结构图表示就是:
在这里插入图片描述 同时Redis为了方便操作链表,提供了一个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;
其中:
在这里插入图片描述
链表在Redis中的应用非常广泛,列表对象的底层实现之一就是链表,此外如发布订阅、慢查询、监视器等功能也用到了链表,我们现在简单想一想为什么使用双端无环链表,而不是数组、单向链表等。既然列表对象的底层实现之一是链表,那么我们可以通过一个表格来分析一下列表对象的常用操作命令,如果分别使用数组、单链表和双端链表实现列表对象的时间复杂度对照如下:
操作\时间复杂度 | 数组 | 单链表 | 双端链表 |
---|---|---|---|
rpush(从右边添加元素) | O(1) | O(1) | O(1) |
lpush(从左边添加元素) | O(n) | O(1) | O(1) |
lpop(从右边删除元素) | O(1) | O(1) | O(1) |
rpop(从左边删除元素) | O(n) | O(1) | O(1) |
lindex(获取指定索引下标的元素) | O(1) | O(n) | O(n) |
len(获取长度) | O(n) | O(n) | O(1) |
linsert(向某个元素前或后插入元素) | O(n) | O(n) | O(1) |
lrem(删除指定元素) | O(n) | O(n) | O(n) |
lset(修改指定索引下标元素) | O(n) | O(n) | O(n) |
但是双向链表因为使用两个额外的空间存储前驱和后继指针,因此在数据流较小的情况下会造成空间上的浪费(因为数据流小的时候速度上差别不大,但空间上差别很大)。这是一个时间换空间还是空间换时间的思想问题。Redis在列表对象中小数据量的时候使用压缩列表来作为底层实现,而大数据量的时候才会使用双向无环链表。
本文首先对链表的相关知识点做了一个回顾,简单的介绍了单链表,双端链表,循环链表。接着就是着重介绍了Redis中的链表结构,Redis的链表采用的是双端无环链表。通过list结构来操作链表。