美文网首页
Redis数据结构学习-链表(二)

Redis数据结构学习-链表(二)

作者: 牛牛_735d | 来源:发表于2020-04-24 17:27 被阅读0次

    链表

    链表提供了高效的节点重排能力, 及顺序性节点访问方式, Redis构建了自己的链表实现

    链表和链表节点的实现

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

    多个listNode节点通过 prevnext指针组成双端链表, 虽然仅使用多个listNode就可以组成链表, 使用 adlist.h/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;
    

    list结构为链表提供了表头指针head、表尾指针tail, 及链表长度计数器len, 而udp, free, match成员则用于实现多态链表所需特定函数.

    Redis 链表实现特性总结
    • 双端: 有prevnext指针, 获取前置和后置节点的复杂度都是O(1)
    • 无环: 表头的prev和表尾的next都指向NULL, 对链表的访问以NULL为终点
    • 带表头和表尾指针: 通过list结构的head和tail指针获取链表的头结点和尾结点复杂度为 O(1)
    • 带长度计数器: 程序使用list结构的len属性对list节点计数, 获取节点数量的复杂度O(1)
    • 多态: 链表节点使用 void *指针保存节点值, 可通过list结构的dup, free, match三个属性为节点值设置类型特定的函数, 所以链表可用来保存不同类型的节点值

    相关文章

      网友评论

          本文标题:Redis数据结构学习-链表(二)

          本文链接:https://www.haomeiwen.com/subject/zdtqwhtx.html