【Redis】数据结构 —— 链表

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,并且可以通过增删节点来灵活调整链表的长度。

因为 Redis 使用的 C 语言并没有内置这种数据结构,所以 Redis 构建了自己的链表实现。

链表在 Redis 中的应用非常广泛,比如列表键list)的底层实现之一就是链表。当一个列表键包含了数据比较多的元素,又或者列表中包含的元素都是比较长的字符串时,Redis 就会使用链表作为列表键的底层实现。

当一个列表键只包含少量列表项,并且每个列表项是小整数值,或者长度比较短的字符串,Redis 使用压缩列表来作为列表键的底层实现。

除了列表键之外,发布订阅慢查询监视器等功能也用到了链表,Redis 服务器本身还使用链表来保存多个客户端的状态信息,已经使用链表来构建客户端输出缓冲区

链表节点(listNode)的实现

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
}

其中:

  • prev:代表当前节点的前置节点
  • next:代表当前节点多个的后置节点
  • value:代表当前节点的值

链表(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);
}

其中:

  • head : 表头节点的指针
  • tail : 表尾节点的指针
  • len : 链表长度计数器
  • dup : 用于复制链表节点所保存的值
  • free : 用于释放链表节点所保存的值
  • match : 用于比较链表节点所保存的值和另一个值是否相等

特性

Redis 的链表实现中,节点都带有 prevnext 指针,且链表中也存储了 head(表头节点指针)和 tail(表尾节点指针),为双向链表,在获取某个节点的前置节点和后置节点的时间复杂度都是 O(1),获取链表的表头节点和表尾节点时间复杂度同样也是 O(1);

但并非是循环链表,因为表头节点的 prev 和表尾节点的 next 指针都指向 null

链表节点中使用 void* 来存储了节点值的指针,并未限制存储类型,可以保存各种不同类型的值

你可能感兴趣的