目录
链表结构设计
编辑链表节点结构设计
链表的优势与缺陷
Redis 的 List 对象的底层实现之一就是链表。C 语言本身没有链表这个数据结构的,所以 Redis 自己设计了一个链表数据结构。
链表结构设计
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;
链表节点结构设计
typedef struct listNode {
//前置节点
struct listNode *prev;
//后置节点
struct listNode *next;
//节点的值
void *value;
} listNode;
有前置节点和后置节点,本质为双向链表
链表的优势与缺陷
Redis 的链表实现优点如下:
- listNode 链表节点的结构里带有 prev 和 next 指针,获取某个节点的前置节点或后置节点的时间复杂度只需O(1),而且这两个指针都可以指向 NULL,所以链表是无环链表;
- list 结构因为提供了表头指针 head 和表尾节点 tail,所以获取链表的表头节点和表尾节点的时间复杂度只需O(1);
- list 结构因为提供了链表节点数量 len,所以获取链表中的节点数量的时间复杂度只需O(1);
- listNode 链表节使用 void* 指针保存节点值,并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数,因此链表节点可以保存各种不同类型的值;
链表的缺陷:
链表每个节点之间的内存都是不连续的,意味着无法很好利用 CPU 缓存,并且容易造成内存碎片化
能很好利用 CPU 缓存的数据结构就是数组,因为数组的内存是连续的,这样就可以充分利用 CPU 缓存来加速访问。文章来源:https://www.toymoban.com/news/detail-570485.html还有一点,保存一个链表节点的值都需要一个链表节点结构头的分配,内存开销较大。文章来源地址https://www.toymoban.com/news/detail-570485.html
到了这里,关于Redis数据结构 — List的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!