Redis學習筆記（二） 鏈表

鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，並且可以通過增刪節點來靈活地調整鏈表的長度。

redis中鏈表應用廣泛，如list中就使用了鏈表。

每一個鏈表節點使用listNode結構標識（雙向鏈表）：

typedef struct listNode{
    //前置節點
    struct listNode *prev;
    //後置節點
    struct listNode *next;
    //節點值
    void *value;
}

鏈表大家都熟悉不做過多說明，再看下list結構的實現：

typedef struct list{
    listNode *head;//表頭節點
    listNode *tail;/表尾節點
    unsigned long len;//鏈表所包含的節點數量
    void *(*dup)(void *ptr);//節點值賦值函數
    void  (*free) (void *ptr);//節點值釋放函數
    int (*match)(void *ptr,void *key);//節點值對比函數
}

Redis 鏈表實現的特點：
1、雙向鏈表，獲取前置後置節點的時間複雜度都是O(1);
2、無環，對鏈表的訪問以NULL為終點。
3、帶有表頭表尾指針，程式獲取鏈表的表頭節點和表尾節點的複雜度為O(1);
4、帶鏈表長度計數器，程式獲取鏈表中節點數量的複雜度為O(1);
5、多態，鏈表節點使用 void* 指針保存節點值，並可以通過list結構的dup、free、match 三個屬性為節點值設置類型特定函數，所以鏈表可以用於保存各種不類型的值。同

t說明：尊重作者知識產權，文中內容參考《Redis設計與實現》，僅在此做學習與大家分享。