首页 > 代码库 > Redis设计与实现 (二): 链表
Redis设计与实现 (二): 链表
Redis实现为双链表结构, 列表键的底层实现之一就是链表, 发布与订阅, 慢查询, 监视器等功能都用到了链表. Redis本身也使用链表维持多个客户端.
节点定义, 位于 adlist.h/listNode
typedef struct listNode { // 前置节点 struct listNode *prev; // 后置节点 struct listNode *next; // 节点的值 void *value; } listNode;
链表结构定义, 位于adlist.h/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;
Redis链表特性总结 :
- 双端链表, 获取前驱和后置都为O(1);
- 无环, 表头的前驱和表尾的后置都为NULL;
- 带头指针和尾指针;
- 带链表长度计数器;
- 多态, void * 保存点值, 通过list结构的dup, free, match三个属性设置节点特定函数, 所以可以用链表保存不同类型的值.
Redis设计与实现 (二): 链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。