學習筆記-Redis設計與實作-連結清單 3.1 連結清單和連結清單節點的實作 3.2 連結清單和連結清單節點的API 3.3 重點回顧

連結清單提供了高效的節點重排能力，以及順序性的節點通路方式，并且可以通過删除節點來靈活地調整連結清單地長度。

當一個清單鍵包含了數量比較多地元素，又或者清單中包含的元素都是比較長的字元串時，Redis就會使用連結清單作為清單鍵的底層實作。

出了連結清單鍵之外，釋出與訂閱、慢查詢、螢幕等功能也用到了連結清單，Redis伺服器本身還使用連結清單來儲存多個用戶端的狀态資訊，以及使用連結清單來建構用戶端輸出緩沖區(Output buffer)

<a href="http://s1.51cto.com/wyfs02/M00/8D/61/wKiom1iaZuHhYTF2AATVO-jZaBs708.png" target="_blank"></a>

<a href="http://s1.51cto.com/wyfs02/M01/8D/61/wKiom1iaZwXycrk1AATVOzkDc08001.png" target="_blank"></a>

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

雙端：連結清單節點帶有prev和next指針，擷取某個節點的前置節點和後置節點的複雜度都是O(1)

無環：表頭節點的prev指針和表尾節點的next指針都指向NULL，對連結清單的通路以NULL為重點。

帶表頭指針和表尾指針：通過list結構的head指針和tail指針，程式擷取連結清單的表頭節點和表尾節點的複雜度為O(1)

帶連結清單長度計數器：程式使用list結構的len屬性來對list持有的連結清單節點進行計數，程式擷取連結清單中節點數量的複雜度為O(1)

多态：連結清單節點使用void*指針來儲存節點值，并且可以通過list結構的dup、free、match三個屬性為節點值設定類型特定函數，是以連結清單可以用于儲存各種不同類型的值。

<a href="http://s3.51cto.com/wyfs02/M00/8D/5F/wKioL1iaZ4jBz187AAdTMXNpkso223.png" target="_blank"></a>

<a href="http://s3.51cto.com/wyfs02/M01/8D/61/wKiom1iaZ42SMriyAAodDiirN8g520.png" target="_blank"></a>

<a href="http://s5.51cto.com/wyfs02/M01/8D/5F/wKioL1iaZ5CSH9IPAAabiWU3pJ8297.png" target="_blank"></a>

連結清單被廣泛用于實作Redis的各種功能，比如清單鍵、釋出與訂閱、慢查詢、螢幕等。

每個連結清單節點由一個listNode結構來表示，每個節點都有一個指向前置節點和後置節點的指針，是以Redis的連結清單實作是雙端連結清單。

每個連結清單使用一個list結構來表示，這個結構帶有表頭節點指針、表尾節點指針，以及連結清單長度等資訊。

因為連結清單表頭節點的前置節點和表尾節點的後置節點都指向NULL，是以Redis的連結清單實作都是無環連結清單。

通過為連結清單設定不同的類型特定函數，Redis的連結清單可以用于儲存各種不同類型的值。

本文轉自 許大樹 51CTO部落格，原文連結：http://blog.51cto.com/abelxu/1895919，如需轉載請自行聯系原作者