tips:本文參照《redis設(shè)計(jì)與實(shí)現(xiàn)》、《數(shù)據(jù)結(jié)構(gòu)與算法》、redis源碼

鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問(wèn)方式，并且可以通過(guò)增刪節(jié)點(diǎn)來(lái)靈活調(diào)整鏈表的長(zhǎng)度。

因?yàn)閞edis使用C語(yǔ)言并沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)，所以redis構(gòu)建了自己的鏈表實(shí)現(xiàn)。

adlist.h/listNode

typedef struct listNode {

//前置節(jié)點(diǎn)

struct listNode *prev;

//后置節(jié)點(diǎn)

struct listNode *next;

//節(jié)點(diǎn)值

void *value;

} listNode;

多個(gè)listNode通過(guò)prev、next組成雙端列表,如下圖

雖然僅僅使用多個(gè)listNode就可以組成鏈表，但使用adlist.h/list來(lái)持有鏈表的話，操作起來(lái)更方便，尤其是對(duì)head與tail操作（實(shí)際過(guò)程中這兩操作非常頻繁）

typedef struct list {

//表頭節(jié)點(diǎn)

listNode *head;

//表尾節(jié)點(diǎn)

listNode *tail;

//節(jié)點(diǎn)復(fù)制函數(shù)

void *(*dup)(void *ptr);

//節(jié)點(diǎn)釋放函數(shù)

void (*free)(void *ptr);

//節(jié)點(diǎn)值對(duì)比函數(shù)

int (*match)(void *ptr, void *key);

//節(jié)點(diǎn)數(shù)量

unsigned long len;

} list;

接下來(lái)看下有3個(gè)listNode組成的list結(jié)構(gòu)的鏈表

redis鏈表實(shí)現(xiàn)總結(jié)：

1）雙端：鏈表節(jié)點(diǎn)都帶有prev和next指針，獲取某個(gè)節(jié)點(diǎn)的前置、后置節(jié)點(diǎn)的復(fù)雜度都是 O(1)

2) 無(wú)環(huán)，表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的tail指針都指向null，對(duì)鏈表的訪問(wèn)以null為終點(diǎn)

3）擁有head和tail，通過(guò)list結(jié)構(gòu)，程序獲取鏈表的表頭節(jié)點(diǎn)、表尾節(jié)點(diǎn)時(shí)間復(fù)雜度O（1）

4）帶鏈表長(zhǎng)度計(jì)數(shù)器，程序獲取鏈表的節(jié)點(diǎn)數(shù)量時(shí)間復(fù)雜度為O(1)

鏈表和鏈表節(jié)點(diǎn)的API