专栏首页用户7890857的专栏2、Redis数据结构——链表-linkedlist
原创

2、Redis数据结构——链表-linkedlist

链表简介:

因为C语言没有内置链表这种数据结构,所以Redis构建了自己的链表实现。列表键的底层实现之一就是链表。当一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis就会使用链表作为列表键的底层实现。

1、链表实现:

链表节点数据结构:

typedef struct listNode {     
struct listNode *prev; // 前置节点     
struct listNode *next; // 后置节点    
 void *value; // 节点的值 
 }listNode; 

虽然使用多个listNode结构就可以组成链表,但使用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函数则用于对比链表结点所保存的值和另一个输入值是否相等;

2、特性:

  1. 双端:链表结点带有prev和next指针,获取某个节点前置节点和后置节点复制度都是O(1)
  2. 无环:表头结点的prev指针和表尾结点的next指针都指向NULL,对链表的访问以NULL为终点。
  3. 带表头指针和表尾指针:获取表头节点和表尾节点复制度O(1)
  4. 带链表长度计数器:len属性对list持有的链表节点进行计数,获取节点数量复制度O(1)
  5. 多态:使用void* 指针保存节点值,通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

重点回顾

  • 链表被广泛用于实现Redis各种功能,如列表键、发布订阅、慢查询等
  • 每个链表结点由一个listNode结构来表示,每个节点都有一个指向前置节点和后置节点的指针,所以Redis的链表实现是双端链表。
  • 每个链表用一个list结构表示,这个结构带有表头节点指针、表尾节点指针以及链表长度等信息。
  • 因为链表表头前置节点和表尾后置节点都指向NULL,所以Redis的链表实现是无环链表。
  • 通过为链表设置不同类型特定函数,Redis的链表可以用于保存各种不同类型的值。

联系我

最后,欢迎关注我的个人公众号 CodingCode,会不定期更新学习笔记,也欢迎公众号私信,一定知无不言,言无不尽。

公众号

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构(2):链表(上)

    顺序表可以随时存取表中的任意一个元素,但插入和删除操作需要移动大量元素。链式存储线性表时,不需要使用地址连续的存储单元,即不要求逻辑上相邻的元素在物理位置上也相...

    不可言诉的深渊
  • 数据结构(2):链表(下)

    上一回,我讲了一下链表的定义和基本操作的实现;这一会我们来看一下链表相关的一个典型应用:一元多项式!一元多项式的定义

    不可言诉的深渊
  • Redis02-Redis的数据结构之Redis链表

    上一篇文章我们学习了Redis的数据结构之简单动态字符串,这一篇我们接着来学习Redis中另外一个数据结构-链表。链表有很多种,首先,本文会首先回顾一下一些常见...

    码农飞哥
  • 链式存储线性表(LinkedList)数据结构解析

    LinkedList内部是通过链表来实现的 一、节点分析 LinkedList内部是通过链表来实现的,那么就少不了节点,所以在源码中必然能找到这样一个节点。 ...

    于霆霖
  • Redis-05Redis数据结构--链表( linked-list)

    由于是双向链表,所以只能够从左到右,或者从右到左地访问和操作链表里面的数据节点。 但是使用链表结构就意味着读性能的丧失,所以要在大量数据中找到一个节点的操作性能...

    小小工匠
  • Redis源码分析(二)——Redis数据结构-链表

    数据结构——节点 typedef struct listNode{ struct listNode *prev; struct listNode *n...

    大闲人柴毛毛
  • 数据结构基础(三).双链表(2)

    原文地址http://soft.dog/2016/12/14/data-structures-03/

    franket
  • 数据结构基础(二).单链表(2)

    franket
  • 《闲扯Redis四》List数据类型底层编码转换

    Redis 中的 list 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • 《闲扯Redis四》List数据类型底层编码转换

    Redis 中的 list 是我们经常使用到的一种数据类型,根据使用方式的不同,可以应用到很多场景中。

    大道七哥
  • [PHP] 链表数据结构(单链表)

    链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表

    陶士涵
  • Redis 面试百问百答 - 04

    不满足ziplist的条件的,使用linkedlist编码。linkedlist 是哟哥撞断链表,每个节点是一个RedisObject 类型是字符串。

    用户7447819
  • 数据结构:链表

    工程代码 Github: Data_Structures_C_Implemention -- Link List

    半纸渊
  • 数据结构 - 链表

    顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充(插入、删除)时又需要进行数据的搬迁,所以使用起来并不是很灵活。

    忆想不到的晖
  • 数据结构-链表

    Head=(Node *)malloc(sizeof(Node)); //Head

    Wilbur-L
  • 数据结构:链表

    链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。

    灰子学技术
  • 数据结构——链表

    若尘_
  • 数据结构——链表

    用户7631864
  • Redis 的底层数据结构(SDS和链表)

    Redis 是一个开源(BSD许可)的,内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。可能几乎所有的线上项目都会使用到 Redis,无论你是做缓...

    Single

扫码关注云+社区

领取腾讯云代金券