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

Redis 设计与实现之链表 -- 阅读笔记

前言

链表提供了高效的节点重排能力,以及顺序性的节点访问方式,链表在 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 函数的作用如下:

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

list 结构与 listNode 组成的链表

Redis 链表特点总结

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

  • B3log

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

    2593 引用 • 4225 回帖 • 631 关注
  • Redis

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

    119 引用 • 202 回帖 • 876 关注
  • 笔记
    148 引用 • 342 回帖
  • 链表
    8 引用 • 6 回帖
感谢    关注    收藏    赞同    反对    举报    分享
回帖    
请输入回帖内容...