雙端鏈表
雙端鏈表是redis list類型的實(shí)現(xiàn)之一，另一種是壓縮列表荐糜。因?yàn)殡p端鏈表占的內(nèi)存比較高巷怜，一般都是優(yōu)先壓縮列表，有需要時(shí)再轉(zhuǎn)換為雙端鏈表暴氏。
雙端鏈表的應(yīng)用范圍
- 事務(wù)模塊使用雙端鏈表依序保存輸入的命令延塑。
- 服務(wù)器模塊用來(lái)保存多個(gè)客戶端。
- 訂閱/發(fā)送模塊來(lái)保存訂閱模式的多個(gè)客戶端答渔。
- 事件模塊使用來(lái)保存時(shí)間事件关带。
雙端鏈表的數(shù)據(jù)結(jié)構(gòu)組成
typedef struct listNode {
// 前驅(qū)節(jié)點(diǎn)
struct listNode *prev;
// 后繼節(jié)點(diǎn)
struct listNode *next;
// 值
void *value;
} listNode;
typedef struct list {
// 表頭指針
listNode *head;
// 表尾指針
listNode *tail;
// 節(jié)點(diǎn)數(shù)量
unsigned long len;
// 復(fù)制函數(shù)
void *(*dup)(void *ptr);
// 釋放函數(shù)
void (*free)(void *ptr);
// 比對(duì)函數(shù)
int (*match)(void *ptr, void *key);
} list;
可以看到，雙端鏈表里面嵌套了一個(gè)雙向鏈表沼撕，使用兩個(gè)指針?lè)謩e指向了這個(gè)雙向鏈表的表頭和表尾宋雏。所以無(wú)論是頭插還是尾插，都不用遍歷鏈表务豺，可以直接進(jìn)行鏈表的操作磨总，時(shí)間復(fù)雜度為O(1)，能高效實(shí)現(xiàn)lpush,rpop,rpoplpush等命令笼沥。
雙端鏈表里還有存儲(chǔ)鏈表節(jié)點(diǎn)數(shù)量的len變量蚪燕，那么對(duì)鏈表長(zhǎng)度的計(jì)算也是O(1)。
