今天小編給大家分享的是redis中的雙端鏈表的數(shù)據(jù)結(jié)構(gòu)與操作，很多人都不太了解，今天小編為了讓大家更加了解Redis中的雙端鏈表，所以給大家總結(jié)了以下內(nèi)容，一起往下看吧。一定會有所收獲的哦。

成都創(chuàng)新互聯(lián)公司是一家專注于成都網(wǎng)站設(shè)計、成都做網(wǎng)站與策劃設(shè)計,裕民網(wǎng)站建設(shè)哪家好?成都創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)10年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:裕民等地區(qū)。裕民做網(wǎng)站價格咨詢:028-86922220

adlist作為Redis中的雙端鏈表，在Redis中被廣泛的應(yīng)用到了很多地方，比如 slowlog的存儲，主從復(fù)制中報錯客戶端，list數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)等，很多都與此相關(guān)，所以也是非常重要的一個數(shù)據(jù)結(jié)構(gòu)。

一）、Redis中雙端鏈表的數(shù)據(jù)結(jié)構(gòu)

雙端鏈表（以下代碼定義在 src/adlist.h）：

typedef struct list {
    listNode *head;    //指向鏈表的第一個節(jié)點(diǎn)
    listNode *tail;    //指向鏈表的最后一個節(jié)點(diǎn)
    //復(fù)制鏈表節(jié)點(diǎn)時候的回調(diào)函數(shù)，由于鏈表節(jié)點(diǎn)可以任意類型的數(shù)據(jù)，不同類型操作不同，故而用回調(diào)函數(shù)去特殊處理
    void *(*dup)(void *ptr);
    void (*free)(void *ptr);     //釋放鏈表節(jié)點(diǎn)內(nèi)存時候的回調(diào)函數(shù)，理由同上
    int (*match)(void *ptr, void *key);    //比較鏈表節(jié)點(diǎn)值的回調(diào)函數(shù)，用于自定義比較，理由同上
    unsigned long len;  //當(dāng)前列表節(jié)點(diǎn)數(shù)量
} list;

雙端鏈表的節(jié)點(diǎn)（以下代碼定義在 src/adlist.h）：

typedef struct listNode {
    struct listNode *prev;   //當(dāng)前節(jié)點(diǎn)的上一個節(jié)點(diǎn)
    struct listNode *next;   //當(dāng)前節(jié)點(diǎn)的下一個節(jié)點(diǎn)
    void *value;     //當(dāng)前節(jié)點(diǎn)存儲的值，可以任意類型
} listNode;

list 通過 head 和 tail兩個指針分別指向鏈表的頭尾兩端，使得遍歷鏈表可以從正反兩個順序進(jìn)行遍歷，而 listNode 的void *value，則可以保存任意數(shù)據(jù)，并可以通過dup，free，match來自定義如何處理listNode的值。

二、雙端鏈表的簡單操作

創(chuàng)建鏈表（以下代碼定義在 src/adlist.c）：

list *listCreate(void)
{
    struct list *list;    //初始化鏈表
    
    //為鏈表分配內(nèi)存
    if ((list = zmalloc(sizeof(*list))) == NULL)
        return NULL;
    //為空鏈表設(shè)置初始值
    list->head = list->tail = NULL;
    list->len = 0;
    list->dup = NULL;
    list->free = NULL;
    list->match = NULL;
    return list;
}

追加到鏈表結(jié)尾（以下代碼定義在 src/adlist.c）：

list *listAddNodeTail(list *list, void *value)
{
    listNode *node;    //初始化node節(jié)點(diǎn)

    //為新的node節(jié)點(diǎn)分配內(nèi)存
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    //為node節(jié)點(diǎn)設(shè)置值
    node->value = value;
    
    if (list->len == 0) {
        //如果空鏈表則 將頭尾指向 新節(jié)點(diǎn) 并后繼前驅(qū)節(jié)點(diǎn)設(shè)置為NULL
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        //否則將節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)設(shè)置為原來的尾部節(jié)點(diǎn)
        node->prev = list->tail;
        //由于追加到尾部，后繼節(jié)點(diǎn)為NULL
        node->next = NULL;
        //之前的尾部節(jié)點(diǎn)的后繼節(jié)點(diǎn)設(shè)置為新增的節(jié)點(diǎn)
        list->tail->next = node;
        //將列表的尾部節(jié)點(diǎn)指針指向新增的節(jié)點(diǎn)
        list->tail = node;
    }
    //增加鏈表長度
    list->len++;
    return list;
}

遍歷鏈表：

常用的遍歷鏈表有兩種方式，一個是根據(jù)鏈表長度通過while循環(huán)去手動遍歷，還有一種是用Redis雙端鏈表提供的迭代器來遍歷。

手動遍歷（以下代碼定義在 src/adlist.c 中的 內(nèi)存釋放函數(shù)）：

void listRelease(list *list)
{
    unsigned long len;
    //current表示當(dāng)前遍歷的游標(biāo)指針，next表示下次遍歷的游標(biāo)指針（next作為臨時變量用于保存下一個節(jié)點(diǎn)）
    listNode *current, *next;
    //將current指向頭部節(jié)點(diǎn)
    current = list->head;
    //計算長度（其實就是 listLength(list)）
    len = list->len;
    //通過長度遞減的方式進(jìn)行遍歷，便利到長度為0的時候，遍歷結(jié)束
    while(len--) {
        //保存下次循環(huán)的節(jié)點(diǎn)指針
        next = current->next;
        //釋放掉當(dāng)前節(jié)點(diǎn)，如果設(shè)置釋放節(jié)點(diǎn)的回調(diào)函數(shù)，則執(zhí)行用戶自定義的函數(shù)
        if (list->free) list->free(current->value);
        zfree(current);
        //將游標(biāo)指向下個節(jié)點(diǎn)
        current = next;
    }
    zfree(list);
}

迭代器方式遍歷請見下文。

三）、雙端鏈表的迭代器

Redis 為了方便對鏈表的迭代，對鏈表進(jìn)行了迭代器的封裝，迭代器結(jié)構(gòu)如下（以下代碼定義在 src/adlist.h）：

typedef struct listIter {
    listNode *next;    //迭代器指向的下一個節(jié)點(diǎn)
    //迭代方向，由于雙端鏈表保存了head和tail的值，所以可以進(jìn)行兩個方向的迭代
    //AL_START_HEAD表示從頭向后遍歷，AL_START_TAIL表示從尾部向前遍歷
    int direction;
} listIter;

迭代器使用實例：

//l表示list結(jié)構(gòu)，n表示listNode結(jié)構(gòu)，listNode的值保存的是sds字符串
//創(chuàng)建迭代器對象
iter = listGetIterator(l, AL_START_HEAD);
//循環(huán)獲取下一個需要遍歷的節(jié)點(diǎn)
while ((n = listNext(iter))) {
    //輸出返回的節(jié)點(diǎn)n的value值
    printf("Node Value: %s\n", listNodeValue(n));
}

以上就是Redis中的雙端鏈表的數(shù)據(jù)結(jié)構(gòu)與操作的簡略介紹，當(dāng)然詳細(xì)使用上面的不同還得要大家自己使用過才領(lǐng)會。如果想了解更多，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道哦！

本文題目：Redis中的雙端鏈表的數(shù)據(jù)結(jié)構(gòu)與操作
文章地址：http://www.rwnh.cn/article24/psghje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、網(wǎng)頁設(shè)計公司、網(wǎng)站導(dǎo)航、標(biāo)簽優(yōu)化、企業(yè)建站、品牌網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)