鏈表提供了高效的節(jié)點(diǎn)重排能力，以及順序性的訪問方式，并且可以通過增刪節(jié)點(diǎn)來靈活的調(diào)整鏈表的長(zhǎng)度

Redis使用c語言并沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)，所以Redis構(gòu)建了自己的鏈表實(shí)現(xiàn)

當(dāng)一個(gè)列表鍵包含了數(shù)量比較多的元素，又或者列表中包含的元素都是比較長(zhǎng)的字符串時(shí)，Redis就會(huì)使用鏈表作為列表的鍵的底層實(shí)現(xiàn)

鏈表的使用

列表鍵
發(fā)布與訂閱
慢查詢
監(jiān)視器
Redis服務(wù)器本身使用鏈表來保存多個(gè)客戶端的狀態(tài)信息
使用鏈表來構(gòu)建客戶端輸出緩沖區(qū)

鏈表與鏈表節(jié)點(diǎn)

鏈表節(jié)點(diǎn)adlist.h/listNode
多個(gè)listNode可以通過prev和next指針組成雙端鏈表

typedef struct listNode{
  //前置節(jié)點(diǎn)
  struct listNode *prev;
  //后置節(jié)點(diǎn)
  struct listNode *next;
  //節(jié)點(diǎn)的值
  void *value;
}listNode;

鏈表adlist.h/list
list結(jié)構(gòu)為鏈表提供了表頭指針head，表尾指針tail，以及鏈表長(zhǎng)度計(jì)數(shù)器len
dup函數(shù)用于復(fù)制鏈表節(jié)點(diǎn)所保存的值
free函數(shù)用于釋放鏈表節(jié)點(diǎn)所保存的值
match函數(shù)用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等

typedef struct list{
  //表頭節(jié)點(diǎn)
  listNode *head;
  //表尾節(jié)點(diǎn)
  listNode *tail;
  //鏈表所包含的節(jié)點(diǎn)數(shù)量
  unsigned long len;
  //節(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);
}list;

list結(jié)構(gòu)和listNode結(jié)構(gòu)組成的鏈表

Redis鏈表實(shí)現(xiàn)的特性

雙端：鏈表節(jié)點(diǎn)帶有prev和next指針，獲取某個(gè)節(jié)點(diǎn)的前置和后置節(jié)點(diǎn)的復(fù)雜度O(1)

無環(huán)：表頭節(jié)點(diǎn)的prev和表尾節(jié)點(diǎn)的next指針都指向NULL，對(duì)鏈表的訪問以NULL為終點(diǎn)

帶表頭指針和表尾指針：通過list結(jié)構(gòu)的head和tail指針，獲取表頭節(jié)點(diǎn)和表尾節(jié)點(diǎn)的指針的復(fù)雜度為O(1)

帶鏈表長(zhǎng)度計(jì)數(shù)器：len屬性來對(duì)list所持有的鏈表節(jié)點(diǎn)進(jìn)行計(jì)數(shù)，獲取鏈表中節(jié)點(diǎn)數(shù)量的復(fù)雜度O(1)

多態(tài)：鏈表節(jié)點(diǎn)使用void*指針來保存節(jié)點(diǎn)值，并且可以通過list結(jié)構(gòu)的dup，free，match三個(gè)屬性為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值

鏈表和鏈表節(jié)點(diǎn)的API