鏈表作為一種常用的數(shù)據(jù)結(jié)構(gòu)秉宿，提供了高效的節(jié)點(diǎn)重排能力疙剑，以及順序性節(jié)點(diǎn)訪問方式氯迂。并且可以通過增刪來靈活的調(diào)整鏈表的長(zhǎng)度践叠。在許多高級(jí)語言中都有鏈表的實(shí)現(xiàn)。然而嚼蚀，Redis使用了C語言并沒有實(shí)現(xiàn)這種數(shù)據(jù)結(jié)構(gòu)禁灼。因此Redis自己實(shí)現(xiàn)了鏈表。
鏈表和鏈表節(jié)點(diǎn)的實(shí)現(xiàn)
每一個(gè)鏈表使用一個(gè)adlist.h/listNode結(jié)構(gòu)來實(shí)現(xiàn)
typedef struct listNode{
struct listNode *prev; //前置節(jié)點(diǎn)
struct listNode *next; //前置節(jié)點(diǎn)
void *value; //節(jié)點(diǎn)的值
}listNode;
多個(gè)listNode可以通過由prev和next指針組成的雙向鏈表如下圖：
由prev和next指針組成的雙向鏈表
雖然使用listNode結(jié)構(gòu)可以組成雙向鏈表轿曙，但是為了操作方便可以使用adlist.h/list來持有鏈表弄捕。定義如下：
typedef struct list{
listNode * head; //頭結(jié)點(diǎn)
listNode * tail; //尾節(jié)點(diǎn)
unsigned long len; //鏈表所包含的節(jié)點(diǎn)數(shù)量
void *(*dup) (void *ptr); //節(jié)點(diǎn)值復(fù)制函數(shù)
void (*free) (void *ptr); //節(jié)點(diǎn)值釋放函數(shù)
void (*match)(void *ptr,void *key); //節(jié)點(diǎn)值對(duì)比函數(shù)
}list;
list中為鏈表提供了表頭指針head和表尾指針tail以及計(jì)算鏈表持有節(jié)點(diǎn)數(shù)據(jù)量的len，而dup函數(shù)用于復(fù)制鏈表節(jié)點(diǎn)所保存的值导帝，free函數(shù)用于釋放鏈表節(jié)點(diǎn)所保存的值守谓，match函數(shù)用于對(duì)比鏈表節(jié)點(diǎn)保存的的值和；另一個(gè)輸入的值是否相等您单。
由list和listNode組成的鏈表
Redis鏈表的特征
- 雙向：鏈表節(jié)點(diǎn)帶有prev和next指針斋荞，獲取某一個(gè)節(jié)點(diǎn)的前置節(jié)點(diǎn)和后置節(jié)點(diǎn)的復(fù)雜度都是O(1)。
- 無環(huán)：表頭節(jié)點(diǎn)的prev指針和表尾節(jié)點(diǎn)的next指針都指向NULL虐秦，對(duì)鏈表的訪問以NULL結(jié)束平酿。
- 帶表頭和表尾指針：通過list的head和tail指針，程序獲得鏈表的表頭和表尾節(jié)點(diǎn)的復(fù)雜度為O(1)羡疗。
- 帶鏈表長(zhǎng)度計(jì)數(shù)器：通過list的len染服，程序獲取鏈表長(zhǎng)度的復(fù)雜度為O(1)。
- 多態(tài)：鏈表節(jié)點(diǎn)使用void*指針來保存節(jié)點(diǎn)值叨恨，可以通過函數(shù)dup,free,match對(duì)節(jié)點(diǎn)的值進(jìn)行操作柳刮，所以鏈表可以保存不同的類型的值。
總結(jié)
- 鏈表被廣泛用于實(shí)現(xiàn)Redis的各種功能痒钝。如：鏈表鍵秉颗，發(fā)布與訂閱，慢查詢送矩，監(jiān)視器等蚕甥。
鏈表 API
| 函數(shù) | 作用 | 時(shí)間復(fù)雜度 |
|---|---|---|
| listSetDupMethod | 將給定的函數(shù)設(shè)置為鏈表的節(jié)點(diǎn)值復(fù)制函數(shù) | O(1) |
| listGetDupMethod | 返回鏈表當(dāng)前正在使用的節(jié)點(diǎn)值復(fù)制函數(shù) | 復(fù)制函數(shù)可以通過鏈表的 dup 屬性直接獲得， O(1) |
| listSetFreeMethod | 將給定的函數(shù)設(shè)置為鏈表的節(jié)點(diǎn)值釋放函數(shù)栋荸。 | O(1) 菇怀。 |
| listGetFree | 返回鏈表當(dāng)前正在使用的節(jié)點(diǎn)值釋放函數(shù) | 釋放函數(shù)可以通過鏈表的 free 屬性直接獲得， O(1) |
| listSetMatchMethod | 將給定的函數(shù)設(shè)置為鏈表的節(jié)點(diǎn)值對(duì)比函數(shù) | O(1) |
| listGetMatchMethod | 返回鏈表當(dāng)前正在使用的節(jié)點(diǎn)值對(duì)比函數(shù)晌块。 | 對(duì)比函數(shù)可以通過鏈表的 match 屬性直接獲得爱沟， O(1) |
| listLength | 返回鏈表的長(zhǎng)度（包含了多少個(gè)節(jié)點(diǎn)）。 | 鏈表長(zhǎng)度可以通過鏈表的 len 屬性直接獲得匆背， O(1) |
| listFirst | 返回鏈表的表頭節(jié)點(diǎn)呼伸。 | 表頭節(jié)點(diǎn)可以通過鏈表的 head 屬性直接獲得， O(1) |
| listLast | 返回鏈表的表尾節(jié)點(diǎn) | 表尾節(jié)點(diǎn)可以通過鏈表的 tail 屬性直接獲得钝尸， O(1) |
| listPrevNode | 返回給定節(jié)點(diǎn)的前置節(jié)點(diǎn) | 前置節(jié)點(diǎn)可以通過節(jié)點(diǎn)的 prev 屬性直接獲得括享， O(1) |
| listNextNode | 返回給定節(jié)點(diǎn)的后置節(jié)點(diǎn) | 后置節(jié)點(diǎn)可以通過節(jié)點(diǎn)的 next 屬性直接獲得搂根， O(1) |
| listNodeValue | 返回給定節(jié)點(diǎn)目前正在保存的值 | 節(jié)點(diǎn)值可以通過節(jié)點(diǎn)的 value 屬性直接獲得， O(1) |
| listCreate | 創(chuàng)建一個(gè)不包含任何節(jié)點(diǎn)的新鏈表 | O(1) |
| listAddNodeHead | 將一個(gè)包含給定值的新節(jié)點(diǎn)添加到給定鏈表的表頭 | O(1) |
| listAddNodeTail | 將一個(gè)包含給定值的新節(jié)點(diǎn)添加到給定鏈表的表尾 | O(1) |
| listInsertNode | 將一個(gè)包含給定值的新節(jié)點(diǎn)添加到給定節(jié)點(diǎn)的之前或者之后 | O(1) |
| listSearchKey | 查找并返回鏈表中包含給定值的節(jié)點(diǎn) | O(N) 铃辖， N 為鏈表長(zhǎng)度 |
| listIndex | 返回鏈表在給定索引上的節(jié)點(diǎn) | O(N) 剩愧， N 為鏈表長(zhǎng)度 |
| listDelNode | 從鏈表中刪除給定節(jié)點(diǎn) | O(1) |
| listRotate | 將鏈表的表尾節(jié)點(diǎn)彈出，然后將被彈出的節(jié)點(diǎn)插入到鏈表的表頭澳叉， 成為新的表頭節(jié)點(diǎn) | O(1) |
| listDup | 復(fù)制一個(gè)給定鏈表的副本 | O(N) 隙咸， N 為鏈表長(zhǎng)度 |
| listRelease | 釋放給定鏈表，以及鏈表中的所有節(jié)點(diǎn) | O(N)成洗，N 為鏈表長(zhǎng)度 |
