鏈表提供了高效的節(jié)點重排能力稽物，以及順序性的訪問方式鞋吉，并且可以通過增刪節(jié)點來靈活的調(diào)整鏈表的長度
Redis使用c語言并沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)鸦做，所以Redis構(gòu)建了自己的鏈表實現(xiàn)
當(dāng)一個列表鍵包含了數(shù)量比較多的元素，又或者列表中包含的元素都是比較長的字符串時谓着，Redis就會使用鏈表作為列表的鍵的底層實現(xiàn)
鏈表的使用
列表鍵
發(fā)布與訂閱
慢查詢
監(jiān)視器
Redis服務(wù)器本身使用鏈表來保存多個客戶端的狀態(tài)信息
使用鏈表來構(gòu)建客戶端輸出緩沖區(qū)
鏈表與鏈表節(jié)點
鏈表節(jié)點adlist.h/listNode
多個listNode可以通過prev和next指針組成雙端鏈表
typedef struct listNode{
//前置節(jié)點
struct listNode *prev;
//后置節(jié)點
struct listNode *next;
//節(jié)點的值
void *value;
}listNode;
鏈表adlist.h/list
list結(jié)構(gòu)為鏈表提供了表頭指針head泼诱，表尾指針tail，以及鏈表長度計數(shù)器len
dup函數(shù)用于復(fù)制鏈表節(jié)點所保存的值
free函數(shù)用于釋放鏈表節(jié)點所保存的值
match函數(shù)用于對比鏈表節(jié)點所保存的值和另一個輸入值是否相等
typedef struct list{
//表頭節(jié)點
listNode *head;
//表尾節(jié)點
listNode *tail;
//鏈表所包含的節(jié)點數(shù)量
unsigned long len;
//節(jié)點值復(fù)制函數(shù)
void *(*dup)(void *ptr);
//節(jié)點值釋放函數(shù)
void (*free)(void *ptr);
//節(jié)點值對比函數(shù)
int (*match)(void *ptr,void *key);
}list;
Redis鏈表實現(xiàn)的特性
雙端：鏈表節(jié)點帶有prev和next指針漆魔，獲取某個節(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ù)器：len屬性來對list所持有的鏈表節(jié)點進(jìn)行計數(shù)改抡，獲取鏈表中節(jié)點數(shù)量的復(fù)雜度O(1)
多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點值矢炼，并且可以通過list結(jié)構(gòu)的dup，free阿纤，match三個屬性為節(jié)點值設(shè)置類型特定函數(shù)句灌，所以鏈表可以用于保存各種不同類型的值
鏈表和鏈表節(jié)點的API
| 函數(shù) | 作用 | 時間復(fù)雜度 |
|---|---|---|
| listSetDupMethod | 將給定的函數(shù)設(shè)置為鏈表的節(jié)點值復(fù)制函數(shù) | 復(fù)制函數(shù)可以由dup屬性直接獲得O(1) |
| listGetDupMethod | 返回鏈表當(dāng)前正在使用的節(jié)點值復(fù)制函數(shù) | O(1) |
| listSetFreeMethod | 將給定函數(shù)設(shè)置為鏈表的節(jié)點值釋放函數(shù) | 釋放函數(shù)可以由free屬性直接獲取O(1) |
| listGetFree | 返回鏈表當(dāng)前正在使用的節(jié)點值釋放函數(shù) | O(1) |
| listSetMatchMethod | 將給定的函數(shù)設(shè)置為鏈表的節(jié)點值對比函數(shù) | 對比函數(shù)可以通過match屬性直接獲取O(1) |
| listGetMatchMethod | 返回鏈表當(dāng)前正在使用的節(jié)點值對比函數(shù) | O(1) |
| listLength | 返回鏈表長度，就是有多少個節(jié)點 | len屬性獲取O(1) |
| listFirst | 返回鏈表的頭結(jié)點 | head屬性獲取O(1) |
| listLast | 返回鏈表表尾節(jié)點 | tail屬性獲取O(1) |
| listPrevNode | 返回給定節(jié)點的前置節(jié)點 | prev屬性獲取O(1) |
| listNextNode | 返回給定節(jié)點的后置節(jié)點 | next屬性獲取O(1) |
| listNodeValue | 返回給定節(jié)點目前正在保存的值 | value屬性獲取O(1) |
| listCreate | 創(chuàng)建一個不包含任何節(jié)點的鏈表 | O(1) |
| listAddNodeHead | 將一個包含給定值的新節(jié)點添加到給定鏈表的表頭 | O(1) |
| listAddNodeTail | 將一個包含給定值的新節(jié)點添加到給定鏈表的表尾 | O(1) |
| listInsertNode | 將一個包含給定值的新結(jié)點添加到給定節(jié)點的之前或者之后 | O(1) |
| listSearchKey | 查找并返回鏈表中包含給定值的節(jié)點 | O(N),N為鏈表長度 |
| listIndex | 返回鏈表在給定索引上的節(jié)點 | O(N) |
| listDelNode | 從鏈表中刪除給定節(jié)點 | O(N) |
| listRotate | 將鏈表的表尾節(jié)點彈出欠拾，然后將被彈出的節(jié)點插入到鏈表的表頭胰锌，成為新的表頭節(jié)點 | O(1) |
| listDup | 復(fù)制一個給定鏈表的副本 | O(N) |
| listRelease | 釋放給定鏈表，以及鏈表中的所有節(jié)點 | O(N) |
