redis資料結構實作--連結清單（list）

2.連結清單和連結清單節點的實作

每個連結清單節點由一個listNode實作

typeof struct listNode{

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

用list來持有連結清單

typeof struct list{

    //表頭節點
    
    listNode *head;
    
    //表尾節點
    
    listNode *tail;
    
    //連結清單長度
    
    unsigned long len;
    
    //節點值複制函數
    
    void *(*dup)(void *ptr);
    
    //節點值釋放函數
    
    void (*free)(void *ptr)
    
    //節點值對比函數
    
    int (*match)(void *ptr,void *key)
    
}           

redis連結清單的實作特性總結如下：

• 雙端：連結清單節點帶有prev和next指針
• 無環：表頭節點的prev指針和表尾節點的next指針都指向null，通路連結清單以null為終點
• list中帶頭指針和表尾指針：通過list結構中的head和tail指針通路表頭尾節點時間複雜度為O(1)
• 連結清單長度計數器：list結構中有len屬性來記錄連結清單長度，擷取連結清單長度時間複雜度為O(1)
• 連結清單節點void* 指針來儲存節點值，可以通過list結構的dup、free、match三個屬性為節點值設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值。