Redis数据结构 — List

这篇具有很好参考价值的文章主要介绍了Redis数据结构 — List。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

链表结构设计

​编辑链表节点结构设计

链表的优势与缺陷


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数据结构 — List,Redis,数据结构,redis,list

链表的优势与缺陷

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

到了这里,关于Redis数据结构 — List的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Redis原理篇(List底层结构与源码详解)

      第一个参数: *c  当redis客户端与服务端连接成功后,客户端就会被封装成一个client对象,里面包含了用户对redis的命令。比如说\\\" LPUSH  key  k1  k2\\\" 就是客户端的一个命令,redis会把 LPUSH ,key,k1,k2放在一个argv[]数组里面。argv[0] 是LPUSH,argv[1] 是key ,argv[2]是k1,argv[3]是k2 第

    2024年01月22日
    浏览(40)
  • Redis-带你深入学习数据类型list

    目录 1、list列表 2、list相关命令 2.1、添加相关命令:rpush、lpush、linsert 2.2、查找相关命令:lrange、lindex、llen 2.3、删除相关命令:lpop、rpop、lrem、ltrim 2.4、修改相关命令:lset 2.5、阻塞相关命令:blpop、brpop 3、应用场景 3.1、消息队列  3.2、最新列表         redis中list并非是一

    2024年02月09日
    浏览(45)
  • 数据结构之list类

    list是列表类。从list 类开始,我们就要接触独属于 Python 的数据类型了。Python 简单、易用,很大一部分原因就是它对基础数据类型的设计各具特色又相辅相成。 话不多说,让我们开始学习第一个 Python 数据类型一list。 1. list的赋值 输出结果 2. Python中list的知识点 list 类与str类

    2024年01月19日
    浏览(37)
  • 【Redis从头学-5】Redis中的List数据类型实战场景之天猫热销榜单

    🧑‍💻作者名称:DaenCode 🎤作者简介:啥技术都喜欢捣鼓捣鼓,喜欢分享技术、经验、生活。 😎人生感悟:尝尽人生百味,方知世间冷暖。 📖所属专栏:Redis从头学 之前的篇章对Redis的String数据类型已经做出了具体分析,并举例说明了其具体的实战场景本文就结合List数据

    2024年02月12日
    浏览(37)
  • day32 泛型 数据结构 List

     概述         JDK1.5同时推出了两个和集合相关的特性:增强for循环,泛型         泛型可以修饰泛型类中的属性,方法返回值,方法参数, 构造函数的参数 Java提供的泛型类/接口 Collection, List, Set,Iterator 等 自定义的泛型 public class Student H,W {} 自定义的泛型方法 public

    2024年02月09日
    浏览(42)
  • 数据结构编程题:Phone List

    Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers: 段落大意:给定一组电话号码,判断它们是否一致,即没有一个号码是另一个号码的前缀。假设电话目录列出了以下号码: Emergency 911 Alice 97 625 999

    2024年01月22日
    浏览(59)
  • 【Redis】1、学习 Redis 的五大基本数据类型【String、Hash、List、Set、SortedSet】

    🍀 Redis 诞生于2009年,全称是 Re mote D ictionary S erver,远程字典服务器,是一个基于 内存的键值型 NoSQL 数据库 🍀 键值(key-value)型,value 支持多种不同数据结构,功能丰富 🍀 单线程,每个命令具备 原子性 🍀 低延迟,速度快(基于内存、IO 多路复用、良好的编码) 🍀支

    2024年02月11日
    浏览(42)
  • Redis数据类型(list\set\zset)

    \\\"maybe it\\\'s why\\\"          列表类型是⽤来存储多个 有序 的字符串,列表中的每个字符串称为元素(element),⼀个列表最多可以存储个2^32 - 1个元素。在Redis中,可以对列表两端插⼊(push)和弹出(pop),还可以获取指定范围的元素列表、获取指定索引下标的元素等。列表是

    2024年02月11日
    浏览(42)
  • 数据结构与算法 | 链表(Linked List)

    链表(Linked List)是一种线性数据结构,它由一系列节点(Node)组成,每个节点包含两部分:数据和指向下(上)一个节点的引用(或指针)。链表中的节点按照线性顺序连接在一起(相邻节点不需要存储在连续内存位置),不像数组一样存储在连续的内存位置。链表通常由

    2024年02月08日
    浏览(50)
  • 数据结构之List(双向链表)的实现

    方法名 参数 功能 返回 find const T val, int n, listNode * p 区间查找 从p往前数n个节点 指针或NULL const T val, listNode * p 区间查找 从p往前到首节点 const T val 查找 Size void 链表规模 size empty void 判空 bool first void 返回首节点 首节点指针 clear void 清空链表 void insertAsFirst const T val 作为首节

    2024年02月16日
    浏览(47)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包