redis數據結構存儲Linked List設計細節（redis的設計與實現筆記）

redis里擁有一個靈活擴展且獲取表頭表尾複雜度為O(1)的雙端列表，分為list和listNode2部分組成。

list:

1 typedef struct list {//鏈表  
2     listNode *head;//鏈表頭  
3     listNode *tail;//鏈表尾  
4     void *(*dup)(void *ptr); //複製函數指針  
5     void (*free)(void *ptr); //釋放記憶體函數指針  
6     int (*match)(void *ptr, void *key); //比較函數指針  
7     unsigned long len; //鏈表長度  
8 } list; 

 listNode：

1 typedef struct listNode {  
2     struct listNode *prev;//前驅指針  
3     struct listNode *next;//後繼指針  
4     void *value; //節點的值  
5 } listNode;  

 以下是雙向鏈表的實現原理：

list結構存在的意義：
1.獲取首元素和尾元素的時間複雜度為O(1)，且可以選擇向後或向前遍歷鏈表元素
2.獲取元素數量時間複雜度為0(1)，無需遍歷即可快速取出元素數量