Redis数据结构之链表

约定不等于承诺〃 2022-11-05 09:56 144阅读 0赞

# 一：链表和链表节点的实现 #

## 1：每个链表节点使用一个adlist.h/listNode结构来表示： ##

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

多个listNode可以通过prev和next指针组成双端链表，如下图所示。

![20210305234916411.png][]

尽管多个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;

*  dup函数用于复制链表节点所保存的值。
 *  free函数用于释放链表节点所保存的值。
 *  match函数用于对比节点所保存的值和另一个输入的值是否相等。

下图是一个list结构和三个listNode结构组成的链表。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

# 二：Redis链表实现的特点 #

*  双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)。
 *  无环：表头节点的prev指针和表尾的next指针都指向NULL，对链表的访问以NULL为终点。
 *  带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为o(1)。
 *  带链表长度计数器：程序获取list结构的len属性值来获取节点数量，故获取链表节点数量的复杂度为0(1)。
 *  多态：链表节点使用void\*指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

# 三：链表和链表节点的API #

![这里写图片描述][20160913195301989]

![这里写图片描述][20160913195342238]

![这里写图片描述][20160913195637098]

*  listCreate函数实现如下：

/* Create a new list. The created list can be freed with
     * AlFreeList(), but private value of every node need to be freed
     * by the user before to call AlFreeList().
     *
     * On error, NULL is returned. Otherwise the pointer to the new list. */
    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;
    }

*  listSetDupMethod函数实现如下：

#define listSetDupMethod(l,m) ((l)->dup = (m))

*  listFirst函数实现如下：

#define listFirst(l) ((l)->head)

[20210305234916411.png]: /images/20221023/c3d66b8a1e324aefbfc310806fec0fad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221023/6738097becdb41e1a9401636524ac5b8.png
[20160913195301989]: /images/20221023/4b6a6a2593a34528b17d05543fb12cab.png
[20160913195342238]: /images/20221023/e50facbceb07428f8522a1d71dbebeb8.png
[20160913195637098]: /images/20221023/f1959694a45c46adbc8957ff750c3087.png