鏈表的實現(xiàn)方式有很多種，常見的主要有三個，單向鏈表、雙向鏈表、循環(huán)鏈表。

1、單鏈表

1-1

• 結構：第一個部分保存或者顯示關于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址。單向鏈表只可向一個方向遍歷。
• 優(yōu)點：鏈表特性 插入和刪除方便，只需要考慮相鄰節(jié)點指針的變化，因此為常數(shù)級時間復雜度O(1)
• 缺點：查找慢，需要根據(jù)指針一個結點一個結點地依次遍歷，直到找到相應的結點，因此時間復雜度為O(N)。

2、雙向鏈表

1-2

• 結構：每個數(shù)據(jù)結點中都有兩個指針，分別指向直接后繼和直接前驅。
• 優(yōu)點：鏈表特性 插入和刪除方便

• 在有序鏈表中查找某個元素，單鏈表由于只有后繼指針，因此只能從前往后遍歷查找時間復雜度為O(N)，而雙向鏈表可以雙向遍歷。
• 刪除給定指針指向的結點。假設已經(jīng)找到要刪除的節(jié)點，要刪除就必須知道其前驅節(jié)點和后繼節(jié)點，單鏈表想要知道其前驅節(jié)點只能從頭開始遍歷，時間復雜度為0(n)，而雙向鏈表由于保存了其前驅節(jié)點的地址，因此時間復雜度為0(1)。

• 缺點：查找慢，雙向鏈表需要額外的兩個空間來存儲后繼結點和前驅結點的地址。

3、循環(huán)鏈表

1-3

• 結構：一種鏈式存儲結構，它的最后一個結點指向頭結點，形成一個環(huán)。因此，從循環(huán)鏈表中的任何一個結點出發(fā)都能找到任何其他結點。循環(huán)鏈表的操作和單鏈表的操作基本一致，差別僅僅在于算法中的循環(huán)條件有所不同。
• 優(yōu)點：在于鏈尾到鏈頭，鏈頭到鏈尾比較方便適合處理的數(shù)據(jù)具有環(huán)型結構特點。獲取第一個節(jié)點時間復雜度為O(1)，那么獲取最后一個節(jié)點也為O(1) 如 獲取棧頂、棧底、隊頭、隊尾等操作
• 缺點：和其他鏈表差不多

redis 的鏈表結構（adlist.h）

//節(jié)點
typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;
//迭代器
typedef struct listIter {
    listNode *next;
    int direction;
} listIter;
//list 結構
typedef struct list {
    listNode *head;
    listNode *tail;
    //節(jié)點復制函數(shù)
    void *(*dup)(void *ptr);
    //節(jié)點釋放函數(shù)
    void (*free)(void *ptr);
    //節(jié)點比較函數(shù)
    int (*match)(void *ptr, void *key);
    unsigned long len;
} list;

從上面代碼可以看出redis 鏈表是雙向鏈表

/* Add a new node to the list, to head, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
       // 將頭節(jié)點的prev賦值為NULL
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->len++;
    return list;
}
/* Add a new node to the list, to tail, containing the specified 'value'
 * pointer as value.
 *
 * On error, NULL is returned and no operation is performed (i.e. the
 * list remains unaltered).
 * On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{
    listNode *node;
    if ((node = zmalloc(sizeof(*node))) == NULL)
        return NULL;
    node->value = value;
    if (list->len == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        // 將頭節(jié)點的next賦值為NULL
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->len++;
    return list;
}

從listAddNodeTail 和listAddNodeHead 可以看出redis 雙向鏈表是無環(huán)的。

結構特性如下：（網(wǎng)上都這么說）

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

總結

• 采用雙向無環(huán)鏈表而沒有采用其他鏈表 很顯然是一種權衡的策略，那空間來減少鏈表的查詢慢的缺點，典型空間換時間。
• 這種結構跟我們在Java中使用的LinkedList 類似。（鏈表不都這樣嗎？）

應用

除了實現(xiàn)列表類型以外， 雙端鏈表還被很多 Redis 內部模塊所應用：

• 事務模塊使用雙端鏈表依序保存輸入的命令；
• 服務器模塊使用雙端鏈表來保存多個客戶端；
• 訂閱/發(fā)送模塊使用雙端鏈表來保存訂閱模式的多個客戶端；
• 事件模塊使用雙端鏈表來保存時間事件（time event）；