tips:本文參照《redis設(shè)計(jì)與實(shí)現(xiàn)》充甚、《數(shù)據(jù)結(jié)構(gòu)與算法》以政、redis源碼
鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的節(jié)點(diǎn)訪問方式伴找，并且可以通過增刪節(jié)點(diǎn)來靈活調(diào)整鏈表的長(zhǎng)度盈蛮。
因?yàn)閞edis使用C語言并沒有內(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通過prev抖誉、next組成雙端列表,如下圖
雖然僅僅使用多個(gè)listNode就可以組成鏈表，但使用adlist.h/list來持有鏈表的話衰倦，操作起來更方便袒炉，尤其是對(duì)head與tail操作（實(shí)際過程中這兩操作非常頻繁）
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;
接下來看下有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) 無環(huán)我磁，表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的tail指針都指向null，對(duì)鏈表的訪問以null為終點(diǎn)
3）擁有head和tail，通過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
