Redis 数据结构 linkedlist

绝地灬酷狼 2023-10-04 12:30 13阅读 0赞

## 回顾 ##

在上篇博客 [Redis 数据结构 SDS][Redis _ SDS] 中我们介绍了 Redis 的 SDS（Simple Dynamic String，简单动态字符串），今天我们来介绍下 Redis 的 linkedlist（双端链表）。

在真正介绍 Redis 中的 linkedlist 如何实现之前，可以先通过我之前写的 [双向链表][Link 1] 来简单入门下双向链表。

## version：3.0 ##

### 结构 ###

> 以版本为 3.0 的 Redis 源码进行分析，此篇博客中的配图来自 [Redis 设计与实现图片集][Redis]。

老规矩，直接看源码吧，地址：[3.0/src/adlist.h][3.0_src_adlist.h]

#### 结点 ####

先来说下构成链表的基础部分，对应 adlist.h 中的 `listNode`：

typedef struct listNode {
        
    	// 前驱结点
        struct listNode *prev;
        // 后继结点
        struct listNode *next;
        // 结点值
        void *value;
    } listNode;

如上代码所示，一个结点会有重要的三个部分，分别为前驱结点、后继结点以及结点的值（双向链表的 ADT 就是上面的），多个结点构成一双向链表，如下图：  
![在这里插入图片描述][20210504015610665.png]

以为这形成上图所示的链表就结束了吗？不，咱们只是刚开始。

#### 链表 ####

下述代码对应 adlist.h 中的 `list`：

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;

大概的图就是下面这样的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]

这个时候就发现不一样了，咱们普通的链表不是一般就是由多个结点构成的吗，在 Redis 中的链表双向链表咋还专门存了头结点、尾节点、以及当前链表的结点数量呢？

### 分析 ###

回想下之前说到的 [算法时间复杂度][Link 2] 和 [算法空间复杂度][Link 3]，是不是有个 `空间换时间` 的思想。

这个时候就是 `空间换时间` 的一具体体现，我用专门的空间存下当前链表的头结点、存下当前链表的尾结点、存下当前链表的结点数量，是不是就类似于咱们之前说到的 [线性表][Link 4]，我想获取某个头结点、尾结点以及当前的结点数量的时间复杂度为 O( 1 1 1) 了。

## version：3.2+ ##

待写……（将 3.0 的相关源码整理后再着手进行 3.2+ 源码的阅读整理）

## 关联阅读 ##

[Redis 基础][Redis 1]

[Redis 数据结构 SDS][Redis _ SDS]

[Redis 数据结构 linkedlist][Redis _ linkedlist]

[Redis 数据结构 hashtable][Redis _ hashtable]

[Redis 数据结构 skiplist][Redis _ skiplist]

[Redis 数据结构 ziplist][Redis _ ziplist]

[Redis 数据结构 intset][Redis _ intset]

[Redis 数据结构 quicklist][Redis _ quicklist]

[Redis 对象 RedisObject][Redis _ RedisObject]

[Redis _ SDS]: https://mindartisan.blog.csdn.net/article/details/115283999
[Link 1]: https://mindartisan.blog.csdn.net/article/details/114501996
[Redis]: http://1e-gallery.redisbook.com/
[3.0_src_adlist.h]: https://github.com/redis/redis/blob/3.0/src/adlist.h
[20210504015610665.png]: https://img-blog.csdnimg.cn/20210504015610665.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210504015834610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70
[Link 2]: https://mindartisan.blog.csdn.net/article/details/112691301
[Link 3]: https://mindartisan.blog.csdn.net/article/details/113058696
[Link 4]: https://mindartisan.blog.csdn.net/article/details/113271849
[Redis 1]: https://mindartisan.blog.csdn.net/article/details/110290715
[Redis _ linkedlist]: https://mindartisan.blog.csdn.net/article/details/116384345
[Redis _ hashtable]: https://mindartisan.blog.csdn.net/article/details/116562596
[Redis _ skiplist]: https://mindartisan.blog.csdn.net/article/details/117194957
[Redis _ ziplist]: https://mindartisan.blog.csdn.net/article/details/117387561
[Redis _ intset]: https://mindartisan.blog.csdn.net/article/details/118196924
[Redis _ quicklist]: https://mindartisan.blog.csdn.net/article/details/118884060
[Redis _ RedisObject]: https://mindartisan.blog.csdn.net/article/details/119521399