Redis(链表数据结构)

admin2024-04-03  1

LinkNode:

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;

示例
Redis(链表数据结构),在这里插入图片描述,第1张

Redis链表的特性

  1. 双端:listNode 有前置节点和后置节点指针,可以根据指针直接O(1)时间复杂度找到上一个节点和下一个节点。
  2. 无环:列表有头结点和尾节点,在没有数据的时候都是null。没有头尾相连。
  3. 维护链表长度字段。这样在查询该链表长度时不需要再从头结点数到尾节点了这样时间复杂度就由O(n) 变为O(1)。
  4. 带头尾节点这样获取头结点或者尾节点都是O(1)。
  5. 多态:链表节点使用void*指针来保存节点值,并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

总结

  Redis自己实现的链表存储了一些额外的信息,比如头尾节点、长度字段、节点使用的类型。这些都对链表的查询速度进行了优化,设计思想就是以空间换时间

参考:《Redis开发与实现》

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!