前言
??托更了一天，因為新型肺炎疫情的影響，公司昨天開工了。長時間在家里待著，突然開工了。比較不適應，覺得比較疲憊，所以沒更新，對不住，不會逃跑的。今天補上，本來想的是周末補4篇，有點過分了哈哈。
今天要分享的是Redis里面的第二個數(shù)據(jù)結(jié)構(gòu)-鏈表?？瓢喑錾淼拇蠹?，對這個結(jié)構(gòu)都不陌生，所以不會啰嗦太多基礎(chǔ)的東西。
干貨開始
??Redis使用的C語言并沒有鏈表這種結(jié)構(gòu)，所以Redis構(gòu)建了自己的鏈表實現(xiàn)。Redis列表鍵的底層實現(xiàn)之一就是鏈表。當一個鏈表鍵包含了數(shù)量比較多的元素，又或者列表中包含的元素都是比較長的字符串的時候，Redis就會使用鏈表作為列表鍵的底層實現(xiàn)。
??舉個例子，以下展示的integers列表鍵包含了從1到1024共1024個整數(shù)：image.png
??Integers列表鍵的底層實現(xiàn)就是一個鏈表，鏈表中的每個節(jié)點都保存了一個整數(shù)值。
??除了列表鍵之外，發(fā)布與訂閱、慢查詢、監(jiān)視器等功能也用到了鏈表,Redis服務(wù)器 本身還使用鏈表參來保存多個 客戶端的狀態(tài)信息，以及使用鏈表來保存多個客戶端輸出緩沖區(qū) (output buffer )。
??每個鏈表節(jié)點使用一個adlist.h/listNode結(jié)構(gòu)來表示：
typedef struct listNode (
//前置節(jié)點
struct listNode * prev;
//后置節(jié)點
struct listNode * next;
// 節(jié)點的值
void * value;
}listNode;
??多個listNode可以通過prev和next指針組成雙端鏈表:
image.png
??雖然僅僅使用多個listNode結(jié)構(gòu)就可以組成鏈表，但使用adlist.h/list來持有 鏈表的話，操作起來會更方便：
typedef struct list {
//表頭節(jié)點
listNode * head;
//表尾節(jié)點
listNode * tail;
//鏈表所包含的節(jié)點數(shù)量
unsigned long len;
//節(jié)點值復制函數(shù)
void * (*dup) (void *ptr);
//節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
//節(jié)點值對比函數(shù)
int (*match) (void *ptr, void *key);
} list;
list結(jié)構(gòu)為鏈表提供了表頭指針head、表尾指針tail,以及鏈表長度計數(shù)器len, 而dup、free和match成員則是用于實現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)。
- dup函數(shù)用于復制鏈表節(jié)點所保存的值；
- free函數(shù)用于釋放鏈表節(jié)點所保存的值;
- match函數(shù)則用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等
圖3-2是由一個list結(jié)構(gòu)和三個listNode結(jié)構(gòu)組成的鏈表。
image.png
Redis的鏈表實現(xiàn)的特性可以總結(jié)如下：
- 雙端：鏈表節(jié)點帶有prev和next指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是O(1)
- 無環(huán)：表頭節(jié)點的prev指針和表尾節(jié)點的next指針都指向NULL.對鏈表的訪問以NULL為終點。
- 帶表頭指針和表尾指針：通過list結(jié)構(gòu)的head指針和tail指針，程序獲取鏈 表的表頭節(jié)點和表尾節(jié)點的復雜度為O(1)。
- 帶鏈表長度計數(shù)器：程序使用list結(jié)構(gòu)的len屬性來對list持有的鏈表節(jié)點進行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的復雜度為O(1)。
- 多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點值,并且可以通過list結(jié)構(gòu)的dup、 free、match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)，所以鏈表可用于保存各種不同類型的值。
總結(jié)
1.鏈表被廣泛用于實現(xiàn)Redis的各種功能，比如列表鍵、發(fā)布與訂閱、慢査詢、監(jiān)視器等。
2.每個鏈表節(jié)點由一個listNode結(jié)構(gòu)來表示，每個節(jié)點都有一個指向前置節(jié)點和后置節(jié)點的指針,所以Redis的鏈表實現(xiàn)是雙端鏈表。
3.每個鏈表使用一個list結(jié)構(gòu)來表示，這個結(jié)構(gòu)帶有表頭節(jié)點指針、表尾節(jié)點指針， 以及鏈表長度等信息。
4.因為鏈表表頭節(jié)點的前置節(jié)點和表尾節(jié)點的后置節(jié)點都指向NULL,所以Redis的鏈表實現(xiàn)是無環(huán)鏈表。
5.通過為鏈表設(shè)置不同的類型特定函數(shù)，Redis的鏈表可以用于保存各種不同類型的值。
