关于java:深入理解Redis-数据结构双链表

在 Redis 数据类型中的 列表 list，对数据的增加和删除罕用的命令有 lpush,rpush,lpop,rpop，其中 l 示意在左侧，r 示意在右侧，能够在左右两侧做增加和删除操作，阐明这是一个双向的数据结构，而 list 数据结构正是双向链表，相似 java 中的 LinekdList 链表列表。

链表提供了高效的节点重排能力，以及程序的节点拜访形式，通过批改节点的 pre 和 next 指针来批改链表的数据。

C 语言没有内置链表的数据结构，所以 Redis 构建了本人的链表构造。

链表的数据结构，链表以及链表节点

链表是由链表以及链表节点组成，每个链表节点应用一个 adlist.h/listNode 构造来示意：

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

多个 listNode 能够通过 prev 和 next 指针组成双链表的，如题所示：

多个 listNode 能够组成链表，然而为了方便管理，应用 adlist.h/list 治理链表，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;

list 构造为链表提供了表头指针 head、表尾指针 tail，以及节点数量计算 len。下图展现一个由 list 构造和三个 listNode 节点组成的链表：

Redis 链表实现的特色有如下的总结：

• 双向：链表节点带有 prev 和 next 指针，能够通过指针获取每一个数据
• 疾速计算链表长度：通过 list 构造中的 len 属性计算 list 的长度，而工夫复杂度为 O(1)
• 多态：链表节点应用 void* 指针保留节点，所以链表反对保留各种不同类型的值

双链表的使用

列表键，公布订阅、慢查问以及监视器等。

总结

• 本文通过介绍链表的数据结构，链表是由链表和链表节点组成的
• 链表节点都有一个前置和后置指针，所以 Redis 的链表是一个双向链表
• 链表能够存储头结点，尾节点，更好的治理本人的节点，len 属性疾速算出链表的长度
• 链表通过 void* 以及不同的类型设定函数，所以链表能够不同的类型的值

如果感觉文章对你有帮忙的话，请点个赞吧!