前言

鏈表作為一種常用的數(shù)據(jù)結(jié)構(gòu)，會(huì)內(nèi)置在很多高級(jí)的編程語(yǔ)言中，而Redis使用的C語(yǔ)言并沒(méi)有內(nèi)置鏈表數(shù)據(jù)結(jié)構(gòu)，故redis構(gòu)建了自己的鏈表實(shí)現(xiàn)

鏈表特性

1. 順序節(jié)點(diǎn)訪問(wèn)

2. 高效節(jié)點(diǎn)重排

3. 靈活調(diào)整鏈表長(zhǎng)度

redis中的鏈表用途

鏈表在Redis的應(yīng)用十分廣泛，如列表鍵的底層實(shí)現(xiàn)之一就是鏈表

• 列表鍵

• 發(fā)布訂閱

• 慢查詢

• 監(jiān)視器

• 保存客戶端狀態(tài)信息

• 構(gòu)建客戶端輸出緩沖區(qū)

列表鍵

當(dāng)一個(gè)列表鍵包含的元素?cái)?shù)量比較多的時(shí)候（> 512）或列表中包含的元素都是比較長(zhǎng)的字符串的時(shí)候（任一個(gè)元素 > 64字節(jié)），Redis就會(huì)使用鏈表作為列表鍵的底層實(shí)現(xiàn)，否則使用壓縮列表數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)，后續(xù)文章會(huì)介紹

鏈表在redis中的實(shí)現(xiàn)

使用list結(jié)構(gòu)來(lái)表示鏈表，使用listNode來(lái)表示每一個(gè)鏈表節(jié)點(diǎn)

list

typedef struct list {

    // 鏈表頭節(jié)點(diǎn)
    listNode * head;

    // 鏈表尾節(jié)點(diǎn)
    listNode * tail;

    // 鏈表所包含的節(jié)點(diǎn)數(shù)量
    unsiged long len;

    // 操作節(jié)點(diǎn)函數(shù)...
}

listNode

typedef struct listNode {

    // 前置節(jié)點(diǎn)
    struct listNode * prev;

    // 后置節(jié)點(diǎn)
    struct listNode * next;

    // 節(jié)點(diǎn)的值
    void * value;
}

整體結(jié)構(gòu)簡(jiǎn)圖

鏈表結(jié)構(gòu)圖

Redis鏈表特性

• 雙端（每個(gè)節(jié)點(diǎn)都有前置/后置節(jié)點(diǎn)的指針）

• 無(wú)環(huán)（表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的next指針均為null，即對(duì)鏈表的訪問(wèn)以null為終點(diǎn)）

• 帶有表頭指針和表尾指針（head和tail屬性）

• 帶鏈表長(zhǎng)度計(jì)數(shù)器（len屬性）

• 多態(tài)（指的是listNode節(jié)點(diǎn)保存的值的類(lèi)型為void，可以保存各種不同類(lèi)型的值）

總結(jié)

redis中自構(gòu)建的鏈表數(shù)據(jù)結(jié)構(gòu)，主要用于列表鍵的底層實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)