redis 系列4 數據結構之鏈表

一. 概述

　　鏈表提供了高效的節點重排能力，以及順序性的節點訪問方式，並且可能通過增刪節點來靈活地調整鏈表的長度。作為一種數據結構，在C語言中並沒有內置的這種數據結構。所以Redis構建了自己的鏈表實現。鏈表在Redis中應用非常多，比如列表鍵的底層實現之一就是鏈表，當一個列表鍵包含了數量比較多的元素，又或者列表中包含的元素都是比較長的字元串時，Redis就會使用鏈表作為列表鍵的底層實現。

-- 例1：使用integers 列表鍵包含了從1到10，共有10個整數
127.0.0.1:6379> rpush integers "1" "2" "3" "4" "5" "6" "7" "8" "9" "10"
(integer) 10
127.0.0.1:6379> llen integers
(integer) 10
127.0.0.1:6379> lrange integers 0 5
1) "1"
2) "2"
3) "3"
4) "4"
5) "5"
6) "6"

　　integers列表鍵的底層實現就是一個鏈表。鏈表中的每個節點都保存了一個整數值，除了鏈表鍵之外，發佈與訂閱，慢查詢，監視器等功能也用到了鏈表。Redis伺服器本身還使用鏈表來保存多個客戶端的狀態信息，以及使用鏈表來構建客戶端輸出緩衝區(output buffer)。

二 鏈表和鏈表節點定義

// 每個鏈表節點使用一個adlist.h/listNode結構來表示：
      typedef struct listNode
        {
            //前置節點
            struct listNode *prev;
            //後置節點
            struct listNode *next;
            //節點的值
            void *value;
        }listNode; //別名

　　多個listNode可能通過prev和next指針組成雙端鏈表。雖然使用多個listNode結構就可以組成鏈表，但使用adlist.h/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)
        }list; //別名

　　在list結構中鏈表提供了表頭指針head, 表尾指針tail，以及鏈表長度計數器len, 而dup, free和match成員則是用於實現多態鏈表所需的類型特定函數:dup 函數用於複製鏈表節點所保存的值； free 函數用於釋放鏈表節點所保存的值； match 函數則用於對比鏈表節點所保存的值和另一個輸入值是否相等。

三.Redis的鏈表實現的特性總結

　　(1)雙端: 鏈表節點帶有prev 和next 指針，獲取某個節點的前置節點和後置節點的複雜度都是0(1) 。

　　(2)無環: 表頭節點的prev指針和表尾節點的next 指針都指向null ,對鏈表的訪問以null 為終點 。

　　(3)帶表頭指針和表尾指針：通過list結構的head指針和tail 指針，程式獲取鏈接的表頭節點和表尾節點的複雜度為0(1)

　　(4)帶鏈表長度計數器：程式使用list結構的len屬性來對list持有的鏈表節點進行計數，程式獲取鏈表中節點數量的複雜度為0(1)

　　(5)多態:鏈表節點使用void* 指針來保存節點值，並且可能通過list結構的dup,free,match 三個屬性為節點值設置類型特定函數，所以鏈表可以用於保存各種不同類型的值。

四. 鏈表和鏈表節點的API

　　總結:

　　　　(1) 鏈表被廣泛用於實現Redis的各種功能，比如列表鍵，發佈與訂閱，慢查詢，監視器等。

　　　　(2) 每個鏈表節點由一個listNode結構來表示，每個節點都有一個指定前置節點和後置節點的指針，所以Redis的鏈表實現是雙端鏈表。

　　　　(3) 每個鏈表使用一個list結構來表示，這個結構帶有表頭節點指針 ，表尾節點指針，以及鏈表長度等信息。

　　　　(4) 因為鏈表表頭節點的前置節點和表尾節點的後置節點都指向null, 所以Redis的鏈表實現是無環鏈表。

　　　　(5) 通過為鏈表設置不同的類型特定函數，Redis的鏈表可以用於保存各種不同類型的值。