Redis-鏈表
鏈表提供了高效的節(jié)點重排能力茂缚，以及順序性的節(jié)點訪問方式，并且可以通過增刪節(jié)點來靈活的調(diào)整鏈表的長度。
作為一種常用數(shù)據(jù)結(jié)構(gòu)嵌戈，鏈表內(nèi)置在很多高級的編程語言里面，因為Redis使用的c語言并沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)听皿，所以Redis構(gòu)建了自己的鏈表實現(xiàn)熟呛。
鏈表在Redis中的應(yīng)用非常廣泛，比如列表鍵的底層實現(xiàn)之一就是鏈表尉姨。當一個列表鍵包含了數(shù)量比較多的元素庵朝，又或者列表中包含的元素都是比較長的字符串的時，Redis就會使用鏈表作為列表鍵的實現(xiàn)又厉。
舉個例子九府，以下展示的integers列表鍵包含了1-1024共一千零二十四個整數(shù)：
redis> LLEN integers
(integer) 1024
redis> LRANGE integers 0 10
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"
7) "7"
8) "8"
9) "9"
10) "10"
11) "11"
integers列表鍵的底層實現(xiàn)就是一個鏈表，鏈表中的每個節(jié)點都保存了一個整數(shù)值覆致。
除了鏈表鍵之外侄旬，發(fā)布與訂閱、慢查詢煌妈、監(jiān)視器等功能也用到了鏈表儡羔，Redis服務(wù)器本身還是要鏈表保存多個客戶端信息的狀態(tài)信息，以及使用鏈表來構(gòu)建客戶端輸出緩沖區(qū)（output buffer）璧诵。
鏈表和鏈表節(jié)點的實現(xiàn)
每個鏈接節(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指針組成雙端列表汰蜘，如下圖：
雖然僅僅使用多個listNode結(jié)構(gòu)就可以組成鏈表，但使用adlist.h/list來持有鏈表的話腮猖，操作起來會更方便：
typedef struct list {
// 表頭節(jié)點
listNode *head;
// 表尾節(jié)點
listNode *tail;
// 節(jié)點值復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
// 節(jié)點值對比函數(shù)
int (*match)(void *ptr, void *key);
// 鏈表所包含的節(jié)點數(shù)量
unsigned long len;
} list;
list結(jié)構(gòu)為鏈表提供了表頭指針head鉴扫、表尾指針tail，以及鏈表長度計數(shù)器len澈缺，而dup坪创、free和match成員則是用于實現(xiàn)多態(tài)鏈表所需要的類型特定函數(shù)：
-
dup函數(shù)用于復(fù)制鏈表節(jié)點所保存的值； -
free函數(shù)用于釋放鏈表節(jié)點所保存的值姐赡； -
match函數(shù)則用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等莱预；
下圖是由一個list結(jié)構(gòu)和三個listNode結(jié)構(gòu)組成的鏈表。
總結(jié)
Redis的鏈表實現(xiàn)的特性可以總結(jié)如下：
- 雙端：鏈表節(jié)點帶有
prev和next指針项滑，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復(fù)雜度都是O(1)依沮。 - 無環(huán)：表頭節(jié)點的
prev指針和表尾節(jié)點的next指針都指向NULL，對鏈表的訪問以NULL為終點。 - 帶表頭指針和表尾指針：通過
list結(jié)構(gòu)的head指針和tail指針危喉，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復(fù)雜度為O(1)宋渔。 - 帶鏈表長度計數(shù)器：程序使用
list結(jié)構(gòu)的len屬性來對list持有的鏈表節(jié)點進行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的的復(fù)雜度為O(1)辜限。 - 多態(tài)：鏈表節(jié)點使用
void*指針來保存節(jié)點值皇拣，并且可以通過list結(jié)構(gòu)的dup，free薄嫡，match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)氧急，所以鏈表可以用于保存各種不同類型的值。
打賞
如果我的文章對您有幫助：打賞一下喲毫深！傳送門
