鏈表簡(jiǎn)介

鏈表提供了高效的節(jié)點(diǎn)重排能力， 以及順序性的節(jié)點(diǎn)訪問(wèn)方式， 并且可以通過(guò)增刪節(jié)點(diǎn)來(lái)靈活地調(diào)整鏈表的長(zhǎng)度。作為一種常用數(shù)據(jù)結(jié)構(gòu)， 鏈表內(nèi)置在很多高級(jí)的編程語(yǔ)言里面， 因?yàn)?Redis 使用的 C 語(yǔ)言并沒(méi)有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)， 所以 Redis 構(gòu)建了自己的鏈表實(shí)現(xiàn)。

鏈表及鏈表節(jié)點(diǎn)的實(shí)現(xiàn)

• 每個(gè)鏈表節(jié)點(diǎn)使用一個(gè)adlist.h/listNode結(jié)構(gòu)來(lái)表示

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

• Reids還定義了鏈表結(jié)構(gòu)，用于持有鏈表

typedef struct list {
    listNode *head; /* 表頭結(jié)點(diǎn) */
    listNode *tail; /* 表尾結(jié)點(diǎn) */
    void *(*dup)(void *ptr); /* 節(jié)點(diǎn)復(fù)制函數(shù) */
    void (*free)(void *ptr); /* 節(jié)點(diǎn)釋放函數(shù) */
    int (*match)(void *ptr, void *key); 
    unsigned long len; /* 鏈表節(jié)點(diǎn)數(shù)量 */
} list;

list 結(jié)構(gòu)為鏈表提供了表頭指針 head 、表尾指針 tail ， 以及鏈表長(zhǎng)度計(jì)數(shù)器 len ， 而 dup 、 free 和 match 成員則是用于實(shí)現(xiàn)多態(tài)鏈表所需的類型特定函數(shù)：

1. dup 函數(shù)用于復(fù)制鏈表節(jié)點(diǎn)所保存的值；
2. free 函數(shù)用于釋放鏈表節(jié)點(diǎn)所保存的值；
3. match 函數(shù)則用于對(duì)比鏈表節(jié)點(diǎn)所保存的值和另一個(gè)輸入值是否相等。

如圖是由一個(gè)list結(jié)構(gòu)和三個(gè)listNode結(jié)構(gòu)組成的鏈表

list持有l(wèi)istNode示例.png

這樣定義好處是

1. 快速獲取鏈表的頭尾
2. 快速查詢鏈表的節(jié)點(diǎn)數(shù)，像動(dòng)態(tài)字符串sdshr里的len那樣，不用遍歷全部字符就可以獲取字符串的長(zhǎng)度，這里也類似。

• adlist.h/listIter還定義了迭代器

typedef struct listIter {
    listNode *next; /* 當(dāng)前迭代到的節(jié)點(diǎn) */
    int direction; /* 迭代方向 */
} listIter;
/* Directions for iterators 
 *
 * 迭代器進(jìn)行迭代的方向
 */
// 從表頭向表尾進(jìn)行迭代
#define AL_START_HEAD 0
// 從表尾到表頭進(jìn)行迭代
#define AL_START_TAIL 1

可以這樣迭代

iter = listGetIterator(list, AL_START_HEAD);
while ((node = listNext(iter)) != NULL) {
    doSomethingWith(node);
}

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