美文网首页
Redis底层数据结构之双端链表

Redis底层数据结构之双端链表

作者: 后厂村村长 | 来源:发表于2021-09-16 14:35 被阅读0次

前言

Redis的双端链表是基于双向链表实现的,但传统双向链表存在一些问题,比如获取链表长度需要遍历整个链表,时间复杂度是O(n),影响性能,所以Redis在内部自己实现了一套双端链表。

何谓双向链表

双向链表也叫双链表。
双向链表中不仅有指向后一个节点的指针,还有指向前一个节点的指针。
这样可以从任何一个节点访问前一个节点,当然也可以访问后一个节点,以至整个链表。
一般是在需要大批量的另外储存数据在链表中的位置的时候用。
其结构如下图:


来自维基百科-链表.png

Redis版本的双端链表

Redis 为了更方便的操作链表,在链表之上封装了一个链表结构 list:

typedef struct list {
  // 表头结点
  listNode *head;
  // 表尾节点
  listNode *tail;
  // 链表所包含的节点数量
  unsigned long len;
  // 其他函数
  ...
}list;

list 结构为链表提供了表头指针 head, 表尾指针 tail, 以及链表长度的计数器 len. 来方便的对链表进行一个双端的遍历,或者查看链表长度。

list的head和tail分别指向真实链表节点的头尾,链表节点的结构如下:
链表节点的定义:

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

通过这两个结构,我们就可以构造出来一个Redis的链表了,如下图:


《Redis 的设计与实现(第二版)》

Redis 双端链表结构的主要特点:

头尾指向null,所以是无环链表;
封装了 list 结构,保存了链表的头尾指针以及链表长度,可以快速的执行正向或反向遍历;
带有长度计数器,因此对链表长度的统计时间复杂度是 O(1);

____________________感谢阅读____________________

相关文章

  • redis底层数据组织方式

    底层数据结构 redis底层数据结构有:字典、双端链表、压缩链表、整数集合、跳跃表和字典、整数集合、embstr ...

  • Redis有这一篇就够了

    Redis 数据结构 链表:列表建的底层实现(头指针和尾指针的双端链表) 字典:哈希键的底层实现 使用链地址法(数...

  • Redis源码学习基本数据结构之链表

    介绍 双端链表作为一种通用的数据结构,在 Redis 内部使用得非常多,它既是 Redis 列表结构的底层实现之一...

  • 集合-LinkedList解析

    一、概要 Java中底层数据结构是链表、双端链表,Android中数据结构是双向循环链表 非线程安全数据结构,允许...

  • 数据结构 | 其二 链表

    冰河winner - 数据结构之链表 2.1 单向链表 数据结构(一) 单链表的实现-JAVA 2.2 双端链表 ...

  • Redis底层数据结构之双端链表

    前言 Redis的双端链表是基于双向链表实现的,但传统双向链表存在一些问题,比如获取链表长度需要遍历整个链表,时间...

  • 链表

    链表数据结构 Redis的链表实现是双端链表,每个链表节点由一个listNode结构来表示,每个节点都有一个指向前...

  • redis 笔记(双端链表)

    实现 Redis 的列表类型 双端链表还是 Redis 列表类型的底层实现之一, 当对列表类型的键进行操作 —— ...

  • redis双向链表实现(3)

    链表(list)是Redis中最基本的数据结构, 由adlist.h和adlist.c定义事务模块使用双端链表依序...

  • Redis双端链表

    本文摘抄自redis源码学习笔记 双端链表在Redis中的地位:它作为一种通用数据结构,在Redis的内部使用非常...

网友评论

      本文标题:Redis底层数据结构之双端链表

      本文链接:https://www.haomeiwen.com/subject/ohvrgltx.html