鏈表

1. 鏈表和鏈表節(jié)點的實現(xiàn)

每個鏈表節(jié)點使用一個adlist.h/listNode結構來表示

typedef struct listNode{

    // 前置節(jié)點
    struct listNode *prev;

    // 后置節(jié)點
    struct listNode *next;

    // 節(jié)點的值
    void *value;
}listNode;

使用adlist.h/list來持有鏈表的話，操作起來會更方便：

typedef struct list{

    // 表頭節(jié)點
    listNode *head;

    // 表尾節(jié)點
    listNode *tail;

    // 鏈表所包含的節(jié)點數(shù)量
    unsigned long len;

    // 節(jié)點值復制函數(shù)
    void *(*dup)(void *ptr);

    // 節(jié)點值釋放函數(shù)
    void (*free)(void *ptr);

    // 節(jié)點值對比函數(shù)
    int (*match)(void *ptr,void *key);
}list;

Redis鏈表實現(xiàn)的特性如下：

1. 雙端：鏈表節(jié)點帶有prev和next指針，獲取某個節(jié)點的前置節(jié)點和后置節(jié)點的復雜度都是O(1)。
2. 無環(huán)：表頭節(jié)點的prev指針和表尾節(jié)點的next指針都指向NULL，對鏈表的訪問以NULL為終點。
3. 帶表頭指針和表尾指針：通過list結構的head指針和tail指針，程序獲取鏈表的表頭節(jié)點和表尾節(jié)點的復雜度為O(1)。
4. 帶鏈表長度計數(shù)器：程序使用list結構的len屬性來對list持有的鏈表節(jié)點進行計數(shù)，程序獲取鏈表中節(jié)點數(shù)量的復雜度為O(1)。
5. 多態(tài)：鏈表節(jié)點使用void*指針來保存節(jié)點值，并且可以通過list結構的dup、free、match三個屬性為節(jié)點值設置類型特定函數(shù)，所以鏈表可以用于保存各種不同類型的值。

由list結構和listNode結構組成的鏈表

2. 鏈表和鏈表節(jié)點的API