深入聊聊Redis中的雙鏈表

本篇文章帶大家了解一下redis 數據結構中的雙鏈表，簡單介紹一下雙鏈表的運用，希望對大家有所幫助！

在 redis 數據類型中的列表list，對數據的添加和刪除常用的命令有 lpush,rpush,lpop,rpop，其中 l 表示在左側，r 表示在右側，可以在左右兩側做添加和刪除操作，說明這是一個雙向的數據結構，而 list 數據結構正是雙向鏈表，類似 Java 中的 LinekdList 鏈表列表。【相關推薦：Redis視頻教程】

鏈表提供了高效的節點重排能力，以及順序的節點訪問方式，通過修改節點的 pre 和 next 指針來修改鏈表的數據。

C 語言沒有內置鏈表的數據結構，所以 Redis 構建了自己的鏈表結構。

鏈表的數據結構，鏈表以及鏈表節點

鏈表是由鏈表以及鏈表節點組成，每個鏈表節點使用一個 Redis視頻教程 結構來表示：

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

多個 listNode 可以通過 prev 和 next 指針組成雙鏈表的，如題所示：

多個 listNode 可以組成鏈表，但是為了方便管理，使用 Redis視頻教程 管理鏈表，list 結構如下：

typedef?struct?list?{ ????//?列表頭結點 ????listNode?*head; ????//?列表尾結構 ????listNode?*tail; ????//?節點值復制函數 ????void?*(*dup)(void?*ptr); ????//?節點值釋放函數 ????void?(*free)(void?*ptr); ????//?節點值對比函數? ????int?(*match)(void?*ptr,?void?*key); ????//?列表節點數量 ????unsigned?long?len; }?list;

list 結構為鏈表提供了表頭指針 head、表尾指針 tail，以及節點數量計算 len。下圖展示一個由 list 結構和三個 listNode 節點組成的鏈表：

Redis 鏈表實現的特征有如下的總結：

• 雙向：鏈表節點帶有 prev 和 next 指針，可以通過指針獲取每一個數據
• 快速計算鏈表長度：通過 list 結構中的 len 屬性計算 list 的長度，而時間復雜度為O(1)
• 多態： 鏈表節點使用 void* 指針保存節點，所以鏈表支持保存各種不同類型的值

雙鏈表的運用

列表鍵，發布訂閱、慢查詢以及監視器等。

總結

• 本文通過介紹鏈表的數據結構，鏈表是由鏈表和鏈表節點組成的
• 鏈表節點都有一個前置和后置指針，所以 Redis 的鏈表是一個雙向鏈表
• 鏈表可以存儲頭結點，尾節點，更好的管理自己的節點，len 屬性快速算出鏈表的長度
• 鏈表通過 void* 以及不同的類型設定函數，所以鏈表可以不同的類型的值

更多編程相關知識，請訪問：Redis視頻教程！！