Redis数据结构源码解析(五) 双向链表

前言

在Redis3.2版本之前，List 类型的实现是由：压缩列表+双向链表实现的，在3.2版本之后取缔了双向链表。

取缔的原因也很简单，在压缩列表中有讲到。

基本结构

其实双向链表还是很常见的，也没什么不同就是首尾相接的一个个节点。

listNode

typedef struct listNode {

    // 前驱节点
    struct listNode *prev;

    // 后继节点
    struct listNode *next;

    // 值
    void *value;

} listNode;

list

typedef struct list {

    // 表头指针
    listNode *head;

    // 表尾指针
    listNode *tail;

    // 节点数量
    unsigned long len;

    // 复制函数
    void *(*dup)(void *ptr);
    // 释放函数
    void (*free)(void *ptr);
    // 比对函数
    int (*match)(void *ptr, void *key);
} list;

优劣分析

• 双向链表linkedlist便于在表的两端进行push和pop操作，在插入节点上复杂度很低，但是它的内存开销比较大。
• 它在每个节点上除了要保存数据之外，还要额外保存两个指针；
• 双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。

总结

• Redis 实现了自己的双端链表结构。
• 双端链表主要有两个作用：
  • 作为 Redis 列表类型的底层实现之一（3.2后弃用）
  • 作为通用数据结构，被其他功能模块所使用；
• 双端链表及其节点的性能特性如下：
  • 节点带有前驱和后继指针，访问前驱节点和后继节点的复杂度为 O(1) ，并且对链表的迭代可以在从表头到表尾和从表尾到表头两个方向进行；
  • 链表带有指向表头和表尾的指针，因此对表头和表尾进行处理的复杂度为 O(1)；
  • 链表带有记录节点数量的属性，所以可以在 O(1)复杂度内返回链表的节点数量（长度）；