Redis中的雙端鏈表的數據結構與操作

今天小編給大家分享的是Redis中的雙端鏈表的數據結構與操作，很多人都不太了解，今天小編為了讓大家更加了解Redis中的雙端鏈表，所以給大家總結了以下內容，一起往下看吧。一定會有所收獲的哦。

adlist作為Redis中的雙端鏈表，在Redis中被廣泛的應用到了很多地方，比如 slowlog的存儲，主從復制中報錯客戶端，list數據結構的實現等，很多都與此相關，所以也是非常重要的一個數據結構。

一）、Redis中雙端鏈表的數據結構

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

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;

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

typedef struct listNode {
    struct listNode *prev;   //當前節點的上一個節點
    struct listNode *next;   //當前節點的下一個節點
    void *value;     //當前節點存儲的值，可以任意類型
} listNode;

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

二、雙端鏈表的簡單操作

創建鏈表（以下代碼定義在 src/adlist.c）：

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

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

list *listAddNodeTail(list *list, void *value)
{
    listNode *node;    //初始化node節點

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

遍歷鏈表：

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

手動遍歷（以下代碼定義在 src/adlist.c 中的 內存釋放函數）：

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

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

三）、雙端鏈表的迭代器

Redis 為了方便對鏈表的迭代，對鏈表進行了迭代器的封裝，迭代器結構如下（以下代碼定義在 src/adlist.h）：

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

迭代器使用實例：

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

以上就是Redis中的雙端鏈表的數據結構與操作的簡略介紹，當然詳細使用上面的不同還得要大家自己使用過才領會。如果想了解更多，歡迎關注億速云行業資訊頻道哦！