张坤的个人博客

  • 首页
  • 分类
  • 标签
  • 日志

  • 搜索
Jenkins RabbitMQ Zookeeper IDEA Logstash Kibana ELK NIO Netty Spring Cloud Golang DataX Elasticsearch React Native Mysql H2 Socket Spring Boot Kafka Mybatis Sqlmap Vue Postgresql Docker Vert.x Flutter Flink Redis

Redis 链表

发表于 2020-05-30 | 分类于 Redis | 0 | 阅读次数 37

链表简介

链表(linkedlist)作为一种非常常见的数据结构,List类型就使用了链表作为底层实现之一。它不仅在Redis其它数据结构中使用的非常广泛,而且许多高级语言都内置了这种数据结构,比如:Java中的LinkedList

链表分为 单向链表、双向链表、循环链表 等。链表是一种逻辑上连续,物理上分散的数据结构,比如双向链表中的每一个节点它不仅只保存的当前节点的数据,还用两个属性保存了当前节点的上一个节点(pre)和下一个节点(next)的引用地址,分别叫做节点的前驱和后置。有了这两个属性,就算在链表中的节点在内存块中不是连续的,也可以通过next引用向后遍历下一个节点,当next为NULL时,就知道这是最后一个节点。

链表适合存储大量数据节点,因为内存在系统中会有多个进程在使用,内存分配和回收就会产生大量的内存碎片,当一个非常大的数据结构需要被分配内存的时候,将这些内存碎片重新整理的话是很浪费时间的,竟然如此,为什么不在这些内存碎片的基础上继续使用它呢?链表结构就是为了这种场景应运而生的,如果是单项链表的话,每个节点只要多用一个属性去放它下一个节点的内存地址值就行了,内存地址的大小一般是4byte。

但也意味着每个节点都需要需要多浪费4byte去存储这些和实际数据没什么直接关系的地址值本省也是一种浪费,当节点多的时候,这种浪费更严重。

链表这种设计思想在很多地方都有用到,就是 空间换时间 的一种方式,比如重写一个数组结构,在里面多加个len属性,用来存储数组的长度。原来获取数组的长度需要遍历数组起始位置到结束位置的每个节点,时间复杂度是O(n),现在只需要调用一下len属性就好了,时间复杂度为O(1)。

所以链表也不是万能药,只有最适合的,没有最好的。
linkedlist_1.jpg

Redis链表结构实现

链表节点:

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
  • prev:前驱
  • next:后置
  • value:数据

链表:

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;
  • head:头节点
  • tail:尾节点
  • len:链表长度
  • dup:复制链表节点所保存的值
  • free:释放链表节点所保存的值
  • match:对比链表节点所保存的值和另一个输入值是否相等

Redis中的链表结构是双端双向无环链表
通过head和tail属性程序获取链表的表头节点和表尾节点的复杂度为 O(1)
通过len属性获取链表中节点数量的复杂度为 O(1)

# Jenkins # RabbitMQ # Zookeeper # IDEA # Logstash # Kibana # ELK # NIO # Netty # Spring Cloud # Golang # DataX # Elasticsearch # React Native # Mysql # H2 # Socket # Spring Boot # Kafka # Mybatis # Sqlmap # Vue # Postgresql # Docker # Vert.x # Flutter # Flink # Redis
Redis 压缩列表
Redis 对象
  • 文章目录
  • 站点概览
会Coding的猴子

会Coding的猴子

57 日志
19 分类
28 标签
RSS
Github
Creative Commons
© 2021 会Coding的猴子
由 Halo 强力驱动
|
主题 - NexT.Gemini v5.1.4

湘ICP备18011740号