前言

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,链表在 Redis 中的应用很广泛,比如列表键的底层实现之一就是链表,除此之外,发布与订阅、慢查询、监视器等功能也用到了链表,Redis 服务器本身使用链表保存多个客户端的状态信息,使用链表构建客户端输出缓冲区。

链表的底层实现

学习过算法的同学都知道数据结构中的链表的相关概念了,这里简单介绍一下链表的数据结构:

链表是常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针 (Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到 O(1) 的复杂度,比另一种线性表 顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要 O(n) 的时间,而顺序表相应的时间复杂度分别是 O(logn) 和 O(1)。(来源于维基百科)

几种常用的链表

先来看看一个链表节点的数据结构:

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

多个 listNode (链表节点)通过 prev 和 next 指针组成双向链表

链表

下面使用 list 数据结构来管理链表:

typedef struct list {
    // 表头节点 
    listNode *head; 
    // 表尾节点 
    listNode *tail; 
    // 链表所包含的节点数量 
    unsigned long len; 
    // 节点值复制函数 
    void *(*dup)(void *ptr); 
    // 节点值释放函数 
    void *(*free)(void *ptr); 
    // 节点值对比函数 
    void *(*match)(void *ptr, void *key);
}list;

list 结构为链表提供了表头指针 head, 表尾指针 tail, 以及链表长度计数器 len, 而 dup、free 和 match 函数的作用如下:

  • dup 函数用于复制链表节点所保存的值
  • free 函数用于释放链表节点所保存的值
  • match 函数用于对比链表节点所保存的值与另外一个输入值是否相等

list 结构与 listNode 结构组成的链表

list 结构与 listNode 组成的链表

Redis 链表特点总结

  • 双向: 链表节点都有 prev 和 next 指针,可以获取某个节点的前置节点和后置节点,复杂度为 O(1)
  • 无环:上面图片显示,表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL
  • 带表头指针和表尾指针: 通过 list 结构的 head 和 tail 指针,获取表头节点和表尾节点的复杂度为 O(1)
  • 带链表长度计数器:通过 list 结构的 len 字段记录了 链表中的链表节点 (listNode) 数,获取链表长度的复杂度为 O(1)
  • 多态:链表节点使用 void * 指针来保存节点值,可以通过 list 结构的 dup、free 和 match 属性为节点值设置类型特定函数,所有链表可用于保存不同类型的值

这章内容比较少,基本就是 Redis 设计与实现 原样搬过来的,很容易了解,讲的特别好,主要是做个记录,以后可以翻阅。

  • B3log

    B3log 是一个开源组织,名字来源于“Bulletin Board Blog”缩写,目标是将独立博客与论坛结合,形成一种新的网络社区体验,详细请看 B3log 构思。目前 B3log 已经开源了多款产品:PipeSoloSymWide 等,欢迎大家加入,贡献开源。

    3121 引用 • 3882 回帖 • 656 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    121 引用 • 186 回帖 • 926 关注
  • 笔记
    119 引用 • 261 回帖
  • 链表
    7 引用 • 6 回帖
感谢    关注    收藏    赞同    反对    举报    分享