每個鏈表節點使用一個?`adlist.h/listNode`?結構來表示:
~~~
typedef struct listNode {
// 前置節點
struct listNode *prev;
// 后置節點
struct listNode *next;
// 節點的值
void *value;
} listNode;
~~~
多個?`listNode`?可以通過?`prev`?和?`next`?指針組成雙端鏈表, 如圖 3-1 所示。

雖然僅僅使用多個?`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`?函數則用于對比鏈表節點所保存的值和另一個輸入值是否相等。
圖 3-2 是由一個?`list`?結構和三個?`listNode`?結構組成的鏈表:

Redis 的鏈表實現的特性可以總結如下:
* 雙端: 鏈表節點帶有?`prev`?和?`next`?指針, 獲取某個節點的前置節點和后置節點的復雜度都是??。
* 無環: 表頭節點的?`prev`?指針和表尾節點的?`next`?指針都指向?`NULL`?, 對鏈表的訪問以?`NULL`?為終點。
* 帶表頭指針和表尾指針: 通過?`list`?結構的?`head`?指針和?`tail`?指針, 程序獲取鏈表的表頭節點和表尾節點的復雜度為??。
* 帶鏈表長度計數器: 程序使用?`list`?結構的?`len`?屬性來對?`list`?持有的鏈表節點進行計數, 程序獲取鏈表中節點數量的復雜度為?。
* 多態: 鏈表節點使用?`void*`?指針來保存節點值, 并且可以通過?`list`?結構的?`dup`?、?`free`?、?`match`?三個屬性為節點值設置類型特定函數, 所以鏈表可以用于保存各種不同類型的值。
- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤