Redis数据库链表大概介绍

Redis list 笔记

链表和链表节点的实现

  • 在adlist.h中listNode结构表示链表节点

    1
    2
    3
    4
    5
    6
    typedef struct listNode
    {
    struct listNode *prev; //前置节点
    struct listNode *next; //后置节点
    void *value; //节点的值
    }listNode;
  • 在adlist.h中list结构表示链表头

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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)
  • 无环:表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。
  • 表头保存了表头指针和表尾指针,程序获取链表头节点和尾节点的复杂度为O(1)
  • 表头保存了链表长度,获取链表长度的操作复杂度为O(1)
  • 通过(void*) 保存节点值,可以保存不同类型的值,带有dup,free,match属性,为节点值设置类型特定函数。