鏈表是很常用的數(shù)據(jù)結(jié)構(gòu), 大多數(shù)高級語言都有內(nèi)置的實(shí)現(xiàn). 因?yàn)镃并沒有提供鏈表的實(shí)現(xiàn), 所以Redis就自已實(shí)現(xiàn)了鏈表. 如果有上過數(shù)據(jù)結(jié)構(gòu)與算法或者看過其他語言對鏈表的實(shí)現(xiàn), 那么這一部份理解起來就超級easy. 可以參考 java 的 LinkedList 的實(shí)現(xiàn).

redis 關(guān)于鏈表的實(shí)現(xiàn)主要在 adlist.h 和 adlist.c 兩個(gè)文件

1 adlist.h 源碼解析

1.1 鏈表結(jié)構(gòu)體 list

//鏈表結(jié)構(gòu)體
typedef struct list {
    //鏈表首節(jié)點(diǎn)
    listNode *head;
    //鏈表尾節(jié)點(diǎn)
    listNode *tail;
    //結(jié)構(gòu)體的函數(shù)相當(dāng)于多態(tài), 由具體的對象提供對應(yīng)的函數(shù)實(shí)現(xiàn)
    //鏈表復(fù)制指定節(jié)點(diǎn)的value的值, 值如果是結(jié)構(gòu)體, 則需要對應(yīng)的函數(shù)來拷貝
    void *(*dup)(void *ptr);
    //鏈表釋放指定節(jié)點(diǎn)的value的內(nèi)存的函數(shù), 值如果是結(jié)構(gòu)體, 則需要對應(yīng)的函數(shù)釋放內(nèi)存
    void (*free)(void *ptr);
    //值的比較函數(shù), 相當(dāng)于 java 的equals, 用于比較結(jié)構(gòu)體是否相等
    int (*match)(void *ptr, void *key);
    //鏈表長度
    unsigned long len;
} list;

• 鏈表結(jié)構(gòu)體中主要有首節(jié)點(diǎn)指針 head , 尾節(jié)點(diǎn)指針 tail , 三個(gè)函數(shù)指針和鏈表長度 len , 首尾節(jié)點(diǎn)主要是為了方便向后和向前遍歷, 鏈表長度主要是為了獲取節(jié)點(diǎn)的數(shù)量的時(shí)間復(fù)雜度為O(1).
• 鏈表結(jié)構(gòu)體中還有三個(gè)函數(shù)指針, 主要是用于對 listNode 中的 value 進(jìn)行復(fù)制, 釋放內(nèi)存和比較是否相等. 這三個(gè)函數(shù)指針有點(diǎn)像多態(tài), 根據(jù)value是不同的值, 從而使用不同實(shí)現(xiàn)的函數(shù).
• 為什么節(jié)點(diǎn)需要三個(gè)函數(shù)指針呢 ? 當(dāng) value 指針是結(jié)構(gòu)體時(shí), 就不能直接判斷, 復(fù)制和釋放內(nèi)存, 需要根據(jù)具體的結(jié)構(gòu)體來做定制化.

1.2 鏈表節(jié)點(diǎn)的結(jié)構(gòu)體 listNode

//鏈表節(jié)點(diǎn)的結(jié)構(gòu)體
typedef struct listNode {
    //前一個(gè)節(jié)點(diǎn)的引用
    struct listNode *prev;
    //下一個(gè)節(jié)點(diǎn)的引用
    struct listNode *next;
    //當(dāng)前節(jié)點(diǎn)的值, 相當(dāng)于 Object 類型
    void *value;
} listNode;

• value是Void *指針, 相當(dāng)于java的Object, 可以存任何類型的值或結(jié)構(gòu)
• 鏈表節(jié)點(diǎn)通過prev指針指向上一個(gè)節(jié)點(diǎn), 通過next指針指向下一個(gè)節(jié)點(diǎn), 從而將所有節(jié)點(diǎn)連在一起, 如下圖:

image.png

1.3 鏈表迭代器結(jié)構(gòu)體 listIter

//鏈表迭代器
typedef struct listIter {
    //當(dāng)前遍歷節(jié)點(diǎn)
    listNode *next;
    //迭代方向, 可以向前或者向后
    int direction;
} listIter;

//前面開始遍歷
#define AL_START_HEAD 0
//后面開始遍歷
#define AL_START_TAIL 1

• next 可以理解為當(dāng)前遍歷的節(jié)點(diǎn), 也可以理解為下一個(gè)節(jié)點(diǎn), 因?yàn)檎{(diào)用 listNext() 方法就是獲取next的值
• direction 表示迭代方向, 主要兩個(gè)值, AL_START_HEAD 表示從 head 節(jié)點(diǎn)向后遍歷, AL_START_TAIL 表示從 tail 節(jié)點(diǎn)向前遍歷

1.4 鏈表頭文件相關(guān)的函數(shù)聲明

/* Functions implemented as macros */
//獲取鏈表長度
#define listLength(l) ((l)->len)
//獲取鏈表第一個(gè)節(jié)點(diǎn)
#define listFirst(l) ((l)->head)
//獲取鏈表最后一個(gè)節(jié)點(diǎn)
#define listLast(l) ((l)->tail)
//獲取鏈表前一個(gè)節(jié)點(diǎn)
#define listPrevNode(n) ((n)->prev)
//獲取鏈表后一個(gè)節(jié)點(diǎn)
#define listNextNode(n) ((n)->next)
//獲取鏈表節(jié)點(diǎn)的值
#define listNodeValue(n) ((n)->value)

//設(shè)置鏈表的復(fù)制函數(shù)
#define listSetDupMethod(l,m) ((l)->dup = (m))
//設(shè)置鏈表結(jié)構(gòu)體的釋放函數(shù)
#define listSetFreeMethod(l,m) ((l)->free = (m))
//設(shè)置鏈表結(jié)構(gòu)體的匹配函數(shù)
#define listSetMatchMethod(l,m) ((l)->match = (m))

//獲取鏈表的復(fù)制函數(shù)
#define listGetDupMethod(l) ((l)->dup)
//獲取鏈表的釋放函數(shù)
#define listGetFreeMethod(l) ((l)->free)
//獲取鏈表的匹配函數(shù)
#define listGetMatchMethod(l) ((l)->match)

/* Prototypes */
//鏈表創(chuàng)建函數(shù)
list *listCreate(void);
//鏈表釋放
void listRelease(list *list);
//清空鏈表
void listEmpty(list *list);
//添加節(jié)點(diǎn)到頭部
list *listAddNodeHead(list *list, void *value);
//添加節(jié)點(diǎn)到尾部
list *listAddNodeTail(list *list, void *value);

//根據(jù)節(jié)點(diǎn)指定位置插入新節(jié)點(diǎn)
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
//刪除指定節(jié)點(diǎn)
void listDelNode(list *list, listNode *node);
//獲取節(jié)點(diǎn)迭代器
listIter *listGetIterator(list *list, int direction);
//獲取迭代器下一個(gè)節(jié)點(diǎn)
listNode *listNext(listIter *iter);
//釋放迭代器
void listReleaseIterator(listIter *iter);
//復(fù)制鏈表
list *listDup(list *orig);
//根據(jù) key 值查找節(jié)點(diǎn)
listNode *listSearchKey(list *list, void *key);
//根據(jù)索引獲取節(jié)點(diǎn)
listNode *listIndex(list *list, long index);
//設(shè)置迭代器, 指定鏈表從head開始遍歷
void listRewind(list *list, listIter *li);
//設(shè)置迭代器, 指定鏈表從tail開始遍歷
void listRewindTail(list *list, listIter *li);
//將鏈表尾節(jié)點(diǎn)變頭節(jié)點(diǎn)
void listRotateTailToHead(list *list);
//將鏈表頭節(jié)點(diǎn)變尾節(jié)點(diǎn)
void listRotateHeadToTail(list *list);
//將鏈表o拼接到鏈表l后面
void listJoin(list *l, list *o);

2 adlist.c 源碼解析

2.1 創(chuàng)建空鏈表函數(shù) listCreate

//創(chuàng)建空鏈表
list *listCreate(void)
{
    //聲明鏈表
    struct list *list;

    //分配鏈表內(nèi)存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //初始化首節(jié)點(diǎn)與尾節(jié)點(diǎn)都為空
    list->head = list->tail = NULL;
    //設(shè)置長度為 0
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

• 分配鏈表內(nèi)存, 然后將所有指針初始化為 NULL, 鏈表長度初始為 0

2.2 清空鏈表節(jié)點(diǎn)函數(shù) listEmpty

//清空鏈表元素, 不回收鏈表對象的內(nèi)存
void listEmpty(list *list)
{
    //鏈表當(dāng)前長度
    unsigned long len;
    //current 當(dāng)前遍歷指針
    //next 下一個(gè)節(jié)點(diǎn)的指針
    listNode *current, *next;

    //獲取首節(jié)點(diǎn)
    current = list->head;
    //獲取鏈表長度
    len = list->len;
    //按長度遍歷
    while(len--) {
        //獲取下一個(gè)節(jié)點(diǎn)
        next = current->next;
        //如果有指定釋放內(nèi)存的函數(shù), 則調(diào)用函數(shù)釋放節(jié)點(diǎn)的值
        if (list->free) list->free(current->value);
        //釋放節(jié)點(diǎn)內(nèi)存
        zfree(current);
        //當(dāng)前指針替換成下一個(gè)節(jié)點(diǎn)
        current = next;
    }
    //首節(jié)點(diǎn)和尾節(jié)點(diǎn)置 NULL
    list->head = list->tail = NULL;
    //長度設(shè)置為 0
    list->len = 0;
}

• 根據(jù)鏈表長度, 遍歷鏈表對節(jié)點(diǎn)進(jìn)行釋放內(nèi)存直到鏈表為空
• 這個(gè)函數(shù)相當(dāng)于刪除所有節(jié)點(diǎn)

2.3 釋放鏈表內(nèi)存函數(shù) listRelease

//釋放鏈表內(nèi)存
void listRelease(list *list)
{
    //清空鏈表
    listEmpty(list);
    //釋放鏈表內(nèi)存
    zfree(list);
}

• 先清空節(jié)點(diǎn), 然后釋放鏈表內(nèi)存

2.4 添加節(jié)點(diǎn)到鏈表頭 listAddNodeHead

//添加節(jié)點(diǎn)到頭部
list *listAddNodeHead(list *list, void *value)
{
    //節(jié)點(diǎn)指針
    listNode *node;

    //分配節(jié)點(diǎn)內(nèi)存, 分配不了則直接返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //設(shè)置節(jié)點(diǎn)的值
    node->value = value;
    //如果鏈表長度為0 , 則表示鏈表為空, 直接指定首節(jié)點(diǎn)和尾節(jié)點(diǎn)
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //設(shè)置當(dāng)前節(jié)點(diǎn)為首節(jié)點(diǎn), 并且加入鏈表中
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    //鏈表長度加 1
    list->len++;
    //返回鏈表
    return list;
}

2.5 添加節(jié)點(diǎn)到鏈表尾

//添加節(jié)點(diǎn)到鏈表尾
list *listAddNodeTail(list *list, void *value)
{
    //聲明節(jié)點(diǎn)
    listNode *node;

    //分配節(jié)點(diǎn)內(nèi)存, 分配不成功, 則返回 NULL
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //設(shè)置節(jié)點(diǎn)的值
    node->value = value;
    //如果鏈表為空
    if (list->len == 0) {
        //初始化鏈表首節(jié)點(diǎn)和尾節(jié)點(diǎn)都為當(dāng)前節(jié)點(diǎn)
        list->head = list->tail = node;
        //當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)都為 NULL
        node->prev = node->next = NULL;
    } else {
        //鏈表不為空
        //設(shè)置原尾節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        node->prev = list->tail;
        //設(shè)置尾節(jié)點(diǎn)為 NULL
        node->next = NULL;
        //鏈表原尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
        list->tail->next = node;
        //更新鏈表的為節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
        list->tail = node;
    }
    //節(jié)點(diǎn)長度加 1
    list->len++;
    //返回鏈表指針
    return list;
}

2.6 根據(jù)原有節(jié)點(diǎn)指定位置插入新節(jié)點(diǎn) listInsertNode

//根據(jù)原有節(jié)點(diǎn)指定位置插入新節(jié)點(diǎn)
list *listInsertNode(list *list, listNode *old_node, void *value, int after) {
    //聲明新的節(jié)點(diǎn)
    listNode *node;

    //新節(jié)點(diǎn)分配內(nèi)存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //設(shè)置新節(jié)點(diǎn)的值
    node->value = value;
    //如果插入old_node的后面
    if (after) {
        //新節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)設(shè)置為舊節(jié)點(diǎn)
        node->prev = old_node;
        //新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)設(shè)置為舊節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        node->next = old_node->next;
        //如果舊節(jié)點(diǎn)是尾節(jié)點(diǎn)
        if (list->tail == old_node) {
            //重置當(dāng)前節(jié)點(diǎn)為尾節(jié)點(diǎn)
            list->tail = node;
        }
    } else {
        //如果插入old_node的前面
        //新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為舊節(jié)點(diǎn)
        node->next = old_node;
        //新節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為舊節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        node->prev = old_node->prev;
        //如果舊節(jié)點(diǎn)為首節(jié)點(diǎn)
        if (list->head == old_node) {
            //更新鏈表首節(jié)點(diǎn)為新的節(jié)點(diǎn)
            list->head = node;
        }
    }
    //更新前面節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為 當(dāng)前節(jié)點(diǎn)
    if (node->prev != NULL) {
        node->prev->next = node;
    }
    //更新后面節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)為 當(dāng)前節(jié)點(diǎn)
    if (node->next != NULL) {
        node->next->prev = node;
    }
    //增加鏈表長度
    list->len++;
    //返回
    return list;
}

2.7 刪除節(jié)點(diǎn) listDelNode

//刪除節(jié)點(diǎn), 主要是各種鏈表操作哈
void listDelNode(list *list, listNode *node)
{
    //如果當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)不為 NULL
    if (node->prev)
        //設(shè)置前一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        node->prev->next = node->next;
    else
        //要?jiǎng)h除的節(jié)點(diǎn)為首節(jié)點(diǎn), 直接將head設(shè)置為下一個(gè)節(jié)點(diǎn)
        list->head = node->next;
    //如果要?jiǎng)h除的節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為 NULL
    if (node->next)
        //將要?jiǎng)h除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn), 重置為當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
        node->next->prev = node->prev;
    else
        //要?jiǎng)h除的節(jié)點(diǎn)是尾節(jié)點(diǎn), 設(shè)置前一個(gè)節(jié)點(diǎn)為尾節(jié)點(diǎn)
        list->tail = node->prev;
    //如果free函數(shù)存在, 釋放節(jié)點(diǎn)value的內(nèi)存
    if (list->free) list->free(node->value);
    //釋放節(jié)點(diǎn)內(nèi)存
    zfree(node);
    //鏈表長度減 1
    list->len--;
}

2.8 獲取鏈表迭代器指針 listGetIterator

//獲取鏈表迭代器指針
listIter *listGetIterator(list *list, int direction)
{
    //聲明迭代器
    listIter *iter;

    //分配迭代器內(nèi)存
    if ((iter = zmalloc(sizeof(*iter))) == NULL) return NULL;
    //如果是前面開始遍歷
    if (direction == AL_START_HEAD)
        //遍歷節(jié)點(diǎn)從head開始
        iter->next = list->head;
    else
        //從后面開始遍歷
        iter->next = list->tail;
    //設(shè)置遍歷方向
    iter->direction = direction;
    //返回指針
    return iter;
}

2.9 釋放迭代器對象內(nèi)存 listReleaseIterator

//釋放迭代器對象
void listReleaseIterator(listIter *iter) {
    zfree(iter);
}

2.10 設(shè)置迭代器

//設(shè)置迭代器, 指定鏈表從head開始遍歷
void listRewind(list *list, listIter *li) {
    li->next = list->head;
    li->direction = AL_START_HEAD;
}

//設(shè)置迭代器, 指定鏈表從 tail 開始遍歷
void listRewindTail(list *list, listIter *li) {
    li->next = list->tail;
    li->direction = AL_START_TAIL;
}

2.11 獲取迭代器下一個(gè)節(jié)點(diǎn) listNext

//獲取迭代器下一個(gè)節(jié)點(diǎn)
listNode *listNext(listIter *iter)
{
    //獲取下一個(gè)節(jié)點(diǎn)
    listNode *current = iter->next;

    //下一個(gè)節(jié)點(diǎn)不為 NULL
    if (current != NULL) {
        //如果是從頭開始遍歷
        if (iter->direction == AL_START_HEAD)
            //遍歷節(jié)點(diǎn)更新為下一個(gè)節(jié)點(diǎn)
            iter->next = current->next;
        else
            //從尾部開始遍歷, 遍歷節(jié)點(diǎn)更新為上一個(gè)節(jié)點(diǎn)
            iter->next = current->prev;
    }
    //返回當(dāng)前節(jié)點(diǎn)
    return current;
}

2.12 復(fù)制鏈表 listDup

//復(fù)制鏈表
list *listDup(list *orig)
{
    //聲明復(fù)制的鏈表
    list *copy;
    //聲明迭代器
    listIter iter;
    //
    listNode *node;

    //創(chuàng)建空鏈表, 為 NULL, 則直接返回 NULL
    if ((copy = listCreate()) == NULL)
        return NULL;
    //繼承原鏈表的相關(guān)函數(shù)
    copy->dup = orig->dup;
    copy->free = orig->free;
    copy->match = orig->match;
    //設(shè)置迭代器從頭開始遍歷
    listRewind(orig, &iter);
    //獲取下一個(gè)節(jié)點(diǎn)
    while((node = listNext(&iter)) != NULL) {
        //值指針
        void *value;

        //如果有復(fù)制value的函數(shù)
        if (copy->dup) {
            //用函數(shù)拷貝值
            value = copy->dup(node->value);
            //如果為空, 則釋放要拷貝的鏈表并且返回 NULL
            if (value == NULL) {
                listRelease(copy);
                return NULL;
            }
        } else
            //沒有拷貝函數(shù), 則直接獲取值
            value = node->value;
        //添加值添加到copy鏈表的尾部, 內(nèi)存分配失敗則釋放copy鏈表的內(nèi)存并返回NULL
        if (listAddNodeTail(copy, value) == NULL) {
            listRelease(copy);
            return NULL;
        }
    }
    //返回拷貝的鏈表
    return copy;
}

2.13 根據(jù)key查節(jié)點(diǎn) listSearchKey

//根據(jù)key查節(jié)點(diǎn)
listNode *listSearchKey(list *list, void *key)
{
    //聲明迭代器
    listIter iter;
    //當(dāng)前節(jié)點(diǎn)
    listNode *node;

    //設(shè)置迭代器
    listRewind(list, &iter);
    //遍歷迭代器, 獲取當(dāng)前節(jié)點(diǎn)
    while((node = listNext(&iter)) != NULL) {
        //如果有比較函數(shù)
        if (list->match) {
            //比較當(dāng)前節(jié)點(diǎn)的值, 相等則返回
            if (list->match(node->value, key)) {
                return node;
            }
        } else {
            //沒有比較函數(shù), 直接用 == 比較, 只能比較數(shù)值
            if (key == node->value) {
                return node;
            }
        }
    }
    //沒找到, 則返回 NULL
    return NULL;
}

2.14 獲取指定下標(biāo)的節(jié)點(diǎn) listIndex

//獲取指定下標(biāo)的節(jié)點(diǎn)
listNode *listIndex(list *list, long index) {
    listNode *n;

    //如果 index 小于 0 , 則從后面遍歷
    if (index < 0) {
        //取正數(shù)
        index = (-index)-1;
        //獲取初始節(jié)點(diǎn)
        n = list->tail;
        //逐個(gè)索引迭代
        while(index-- && n) n = n->prev;
    } else {
        //從前面遍歷
        n = list->head;
        //逐個(gè)索引迭代
        while(index-- && n) n = n->next;
    }
    //返回節(jié)點(diǎn)
    return n;
}

2.15 頭尾節(jié)點(diǎn)互換

//將鏈表尾節(jié)點(diǎn)變頭節(jié)點(diǎn)
void listRotateTailToHead(list *list) {
    //長度小于等于一個(gè)節(jié)點(diǎn), 不處理
    if (listLength(list) <= 1) return;

    /* Detach current tail */
    //獲取鏈表尾節(jié)點(diǎn)
    listNode *tail = list->tail;
    //重置尾節(jié)點(diǎn)為上一個(gè)節(jié)點(diǎn)
    list->tail = tail->prev;
    //重置新的尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為NULL
    list->tail->next = NULL;
    /* Move it as head */
    //設(shè)置head的前一個(gè)節(jié)點(diǎn)為 tail
    list->head->prev = tail;
    //設(shè)置 tail 前一個(gè)節(jié)點(diǎn)為 NULL
    tail->prev = NULL;
    //更新 tail 的下一個(gè)節(jié)點(diǎn)為鏈表的 head
    tail->next = list->head;
    //重置 head 節(jié)點(diǎn)為 tail
    list->head = tail;
}

/* Rotate the list removing the head node and inserting it to the tail. */
//將頭節(jié)點(diǎn)變尾節(jié)點(diǎn), 代碼基本同 listRotateTailToHead 一致
void listRotateHeadToTail(list *list) {
    if (listLength(list) <= 1) return;

    listNode *head = list->head;
    /* Detach current head */
    list->head = head->next;
    list->head->prev = NULL;
    /* Move it as tail */
    list->tail->next = head;
    head->next = NULL;
    head->prev = list->tail;
    list->tail = head;
}

2.16 將鏈表o拼接到鏈表l后面

//將鏈表o拼接到鏈表l后面
void listJoin(list *l, list *o) {
    //如果要合并的鏈表長度為 0, 則不處理
    if (o->len == 0) return;

    //設(shè)置 o 的頭節(jié)點(diǎn)的前節(jié)點(diǎn)為 l 的尾節(jié)點(diǎn)
    o->head->prev = l->tail;

    //如果l的尾節(jié)點(diǎn)不為NULL
    if (l->tail)
        //設(shè)置 l 的尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為 o 的頭節(jié)點(diǎn)
        l->tail->next = o->head;
    else
        //如果l的尾節(jié)點(diǎn)為NULL, 則直接用o的首節(jié)點(diǎn)作用l的首節(jié)點(diǎn)
        l->head = o->head;

    //更新 l 的尾節(jié)點(diǎn)
    l->tail = o->tail;
    //更新l鏈表的長度
    l->len += o->len;

    /* Setup other as an empty list. */
    //清空o鏈表
    o->head = o->tail = NULL;
    o->len = 0;
}

3 小結(jié)

鏈表超級簡單, 實(shí)現(xiàn)上也跟java的LinkedList 差不多.

微信文章鏈表: https://mp.weixin.qq.com/s?__biz=MzI3NDAxNTAzMw==&mid=2247483721&idx=1&sn=e4d7c32ec51cf67824e5fda961c47d55&chksm=eb1b371fdc6cbe09222d867900b6a1d8022380046c94ce292ddc7929615c55538d3454ba3d68&token=697250728&lang=zh_CN#rd

個(gè)人微信: wolfleong

微信公眾號: wolfleong