链表

Redis中是自己实现的链表。链表被广泛用于Redis的各种功能，比如列表键、发布于订阅、慢查询、监视器等。

列表键的底层实现之一就是链表（Redis3.2 之前，在Redis3.2 后被换成了快速列表quicklist）。当一个列表建包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，Reids会使用链表作为列表键的底层实现。(《Redis设计与实现》)

特点

来之《Redis设计与实现》

• 每个链表结点由一个listNode结构来表示，每个结点都由一个指向前置结点和后置结点的指针，所有Redis的链表实现是双端链表。
• 每个链表使用一个list结构来表示，这个结构带有表头结点指针、表位结点指针、已经链表长度等信息。
• 因为链表表头结点的前置节点和表尾结点的后置节点都指向NULL，所以Redis的链表实现是无环链表。
• 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值。

代码结构

// adlist.h// 链表结点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;// 链表的迭代器typedef struct listIter {    listNode *next; // 下一个节点    int direction; // 迭代方向} listIter;

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

部分代码解析

• list *listAddNodeHead(list *list, void *value) 向list中添加链表头:

  /* Add a new node to the list, to head, containing the specified 'value'	 * pointer as value.	 *	 * On error, NULL is returned and no operation is performed (i.e. the	 * list remains unaltered).	 * On success the 'list' pointer you pass to the function is returned. */	list *listAddNodeHead(list *list, void *value)	{	    listNode *node;	    // 为链表节点分配内存	    if ((node = zmalloc(sizeof(*node))) == NULL)	        return NULL;	    // 给链表节点的value赋值	    node->value = value;	    if (list->len == 0) {	        // 如果list本来没有节点，则将表头节点和表尾节点都设置node	        list->head = list->tail = node;	        // 且node的前置和后置节点都是NULL	        node->prev = node->next = NULL;	    } else {	        // 如果list本来已经存在节点	        // 则将node的前置节点设为NULL	        node->prev = NULL;	        // 然后将node的后置节点指向list原本的表头节点	        node->next = list->head;	        // 将list原本的表头节点的前置节点指向node	        list->head->prev = node;	        // 将node设为list的新表头节点	        list->head = node;	    }	    // list的长度加1	    list->len++;	    return list;	}

• list *listInsertNode(list *list, listNode *old_node, void *value, int after)向list中插入节点value，插入位置是old_node，after表示在old_node前还是后:

  list *listInsertNode(list *list, listNode *old_node, void *value, int after) {	    listNode *node;	    // 给要插入的节点node分配内存	    if ((node = zmalloc(sizeof(*node))) == NULL)	        return NULL;	    // node的value赋值	    node->value = value;	    if (after) {	        // 插入到old_node后	        node->prev = old_node;	        node->next = old_node->next;	        if (list->tail == old_node) {	            // 如果old_node原本是表尾节点，则重新将表尾节点指向node	            list->tail = node;	        }	    } else {	        // 插入到old_node前	        node->next = old_node;	        node->prev = old_node->prev;	        if (list->head == old_node) {	            // 如果old_node原本是表头节点，则重新将表尾节点指向node	            list->head = node;	        }	    }	    if (node->prev != NULL) {	        //如果node的前置节点不为NULL，则将node的前置节点的后置节点指向node	        node->prev->next = node;	    }	    if (node->next != NULL) {	        //如果node的后置节点不为NULL，则将node的后置节点的前置节点指向node	        node->next->prev = node;	    }	    // list的长度加1	    list->len++;	    return list;	}

• void listDelNode(list *list, listNode *node)删除list中的节点node：

  /* Remove the specified node from the specified list.	 * It's up to the caller to free the private value of the node.	 *	 * This function can't fail. */	void listDelNode(list *list, listNode *node)	{	    if (node->prev)	        // 如果node有前置节点	        // 则将 node前置节点的后置节点 指向 node的后置节点	        node->prev->next = node->next;	    else	        // 如果node没有前置节点，则说明node是表头节点	        // 将list的表头节点指向 node的后置节点	        list->head = node->next;	    if (node->next)	        // 如果node有后置节点	        // 则将 node的后置节点的前置节点 指向 node的前置节点	        node->next->prev = node->prev;	    else	        // 如果node没有后置节点，则说明node是表尾节点	        // 将list的表尾节点指向 node的前置节点	        list->tail = node->prev;	    // 如果list有free函数，则调用free函数释放node中的value	    if (list->free) list->free(node->value);	    // 释放node的内存	    zfree(node);	    // list长度减1	    list->len--;	}

链表API

参考之《Redis设计与实现》