Redis数据类型之链表

链表的实现

redis的列表的底层实现就是一个双链表，源码在src下的adlist.h和adlist.c

链表的结点数据结构

    /*
     * 双端链表节点
     */
    typedef struct listNode {

        // 前置节点
        struct listNode *prev;

        // 后置节点
        struct listNode *next;

        // 节点的值
        void *value;

    } listNode;

链表数据结构

/* * 双端链表结构 */ 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的具体功能

部分函数的时间复杂度

// 返回给定链表所包含的节点数量 // T = O(1) #define listLength(l) ((l)->len) // 返回给定链表的表头节点 // T = O(1) #define listFirst(l) ((l)->head) // 返回给定链表的表尾节点 // T = O(1) #define listLast(l) ((l)->tail) // 返回给定节点的前置节点 // T = O(1) #define listPrevNode(n) ((n)->prev) // 返回给定节点的后置节点 // T = O(1) #define listNextNode(n) ((n)->next) // 返回给定节点的值 // T = O(1) #define listNodeva lue(n) ((n)->value) // 将链表 l 的值复制函数设置为 m // T = O(1) #define listSetDupMethod(l,m) ((l)->dup = (m)) // 将链表 l 的值释放函数设置为 m // T = O(1) #define listSetFreeMethod(l,m) ((l)->free = (m)) // 将链表的对比函数设置为 m // T = O(1) #define listSetMatchMethod(l,m) ((l)->match = (m)) // 返回给定链表的值复制函数 // T = O(1) #define listGetDupMethod(l) ((l)->dup) // 返回给定链表的值释放函数 // T = O(1) #define listGetFree(l) ((l)->free) // 返回给定链表的值对比函数 // T = O(1) #define listGetMatchMethod(l) ((l)->match)

/* * 创建一个新的链表 * * 创建成功返回链表，失败返回 NULL 。 * * T = O(1) */ list *listCreate(void) { struct list *list; // 分配内存 if ((list = zmalloc(sizeof(*list))) == NULL) return NULL; // 初始化属性 list->head = list->tail = NULL; list->len = 0; list->dup = NULL; list->free = NULL; list->match = NULL; return list; }

注意，这里的分配 malloc函数，是自己实现的zmalloc