本文共 6008 字，大约阅读时间需要 20 分钟。

基于Redis5.0

链表提供了高效的节点重排能力， 以及顺序性的节点访问方式， 并且可以通过增删节点来灵活地调整链表的长度

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

//adlist.h  - A generic doubly linked list implementation/* Node, List, and Iterator are the only data structures used currently. */typedef struct listNode {
       struct listNode *prev;    struct listNode *next;    void *value;} listNode;

虽然仅仅使用多个 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的迭代器Iterator，用来方便快速遍历list：

typedef struct listIter {
       listNode *next;    //遍历方向    int direction;} listIter;/* Directions for iterators */#define AL_START_HEAD 0#define AL_START_TAIL 1

与Java集合中的Iterator概念类似

Redis 的链表实现的特性可以总结如下：

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

更方便的宏定义：

/* Functions implemented as macros */#define listLength(l) ((l)->len)#define listFirst(l) ((l)->head)#define listLast(l) ((l)->tail)#define listPrevNode(n) ((n)->prev)#define listNextNode(n) ((n)->next)#define listNodeValue(n) ((n)->value)#define listSetDupMethod(l,m) ((l)->dup = (m))#define listSetFreeMethod(l,m) ((l)->free = (m))#define listSetMatchMethod(l,m) ((l)->match = (m))#define listGetDupMethod(l) ((l)->dup)#define listGetFree(l) ((l)->free)#define listGetMatchMethod(l) ((l)->match)

链表API：

创建一个新链表：

/* 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;}

移除链表里的所有元素：

/* Remove all the elements from the list without destroying the list itself. */void listEmpty(list *list){
       unsigned long len;    listNode *current, *next;    current = list->head;    len = list->len;    while(len--) {
           next = current->next;        if (list->free) list->free(current->value);        zfree(current);        current = next;    }    list->head = list->tail = NULL;    list->len = 0;}

添加一个元素到链表头：

/* 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;    node->value = value;    if (list->len == 0) {
           list->head = list->tail = node;        node->prev = node->next = NULL;    } else {
           node->prev = NULL;        node->next = list->head;        list->head->prev = node;        list->head = node;    }    list->len++;    return list;}

删除一个指定节点：

/* 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->prev->next = node->next;    else        list->head = node->next;    if (node->next)        node->next->prev = node->prev;    else        list->tail = node->prev;    if (list->free) list->free(node->value);    zfree(node);    list->len--;}

这里对链表的增删改查如果之前学习过数据结构就非常容易理解了

获取链表的迭代器Iterator：

/* Returns a list iterator 'iter'. After the initialization every * call to listNext() will return the next element of the list. * * This function can't fail. */listIter *listGetIterator(list *list, int direction){
       listIter *iter;    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;    if (direction == AL_START_HEAD)        iter->next = list->head;    else        iter->next = list->tail;    iter->direction = direction;    return iter;}

通过链表的迭代器Iterator获取链表的下一个元素：

/* Return the next element of an iterator. * It's valid to remove the currently returned element using * listDelNode(), but not to remove other elements. * * The function returns a pointer to the next element of the list, * or NULL if there are no more elements, so the classical usage patter * is: * * iter = listGetIterator(list,
   
    ); * while ((node = listNext(iter)) != NULL) { *     doSomethingWith(listNodeValue(node)); * } * * */listNode *listNext(listIter *iter){
       listNode *current = iter->next;    if (current != NULL) {
           if (iter->direction == AL_START_HEAD)            iter->next = current->next;        else            iter->next = current->prev;    }    return current;}
   

搜索返回给定值的节点：

/* Search the list for a node matching a given key. * The match is performed using the 'match' method * set with listSetMatchMethod(). If no 'match' method * is set, the 'value' pointer of every node is directly * compared with the 'key' pointer. * * On success the first matching node pointer is returned * (search starts from head). If no matching node exists * NULL is returned. */listNode *listSearchKey(list *list, void *key){
       listIter iter;    listNode *node;    listRewind(list, &iter);    while((node = listNext(&iter)) != NULL) {
           if (list->match) {
               if (list->match(node->value, key)) {
                   return node;            }        } else {
               if (key == node->value) {
                   return node;            }        }    }    return NULL;}

转载地址：http://luhpi.baihongyu.com/