Redis系列(二)底層數據結構之雙端鏈表

2020 年 1 月 16 日
筆記

前言

Redis 已經是大家耳熟能詳的東西了，日常工作也都在使用，面試中也是高頻的會涉及到，那麼我們對它究竟了解有多深刻呢？

我讀了幾本 Redis 相關的書籍，嘗試去了解它的具體實現，將一些底層的數據結構及實現原理記錄下來。

本文將介紹 Redis 中最基礎的 linkedlist(雙端鏈表) 的實現方法。它是 Redis 的列表鍵的底層實現之一。

如果你對鏈表的基礎定義沒有一些了解的話，建議先去簡單學習一下。

定義

鏈表，是一個非常常用的數據結構，在很多程式語言里都有實現，比如 Java 中的 LinkedList. 但是 C 語言沒有。而 Redis 又需要頻繁的使用鏈表，所以 Redis 自己實現了一個雙端鏈表。

鏈表節點的定義：

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

通過這個節點，我們就可以構造出來一個鏈表了。

但是 Redis 為了更好的操作，封裝了一個鏈表結構 list. 結構如下：

typedef struct list {    // 表頭結點    listNode *head;    // 表尾節點    listNode *tail;    // 鏈表所包含的節點數量    unsigned long len;    // 其他函數    ...  }list;

list 結構為鏈表提供了表頭指針 head, 表尾指針 tail, 以及鏈表長度的計數器 len. 來方便的對鏈表進行一個雙端的遍歷，或者查看鏈表長度。

下圖是一個 list 結構，其中包含了三個 listNode.

優劣

雙向鏈表

從 listNode 的結構我們可以看到，包含了前直接點和後置節點。所以可以很方便的進行正向和反向的遍歷。

無環鏈表

表頭結點的 prev 指針和表尾結點的 next 指針都只想 null, 所以 Redis 的鏈表是一個無環鏈表。

帶有頭指針和尾指針

在 list 結構中，保存了當前鏈表的表頭指針和表尾指針，因此可以快速的從頭進行遍歷或者從尾部開始遍歷。

帶有長度計數器

list 結構中保存了當前鏈表長度的長度，因此對鏈表長度的統計時間複雜度是 O(1).

總結

鏈表是一個比較常用的數據結構，在很多程式語言中都有實現，讀者們接觸也很多。因此本文沒有專門去強調它的實現方法，而是大概介紹了下 Redis 中的鏈表的一個結構及其主要特性：

Redis 的鏈表是雙端鏈表。
封裝了 list 結構，保存了鏈表的頭尾指針以及鏈表長度。
Redis 的鏈表是無環鏈表。

參考文章

《Redis 的設計與實現（第二版）》

完。

聯繫我

最後，歡迎關注我的個人公眾號【呼延十】，會不定期更新很多後端工程師的學習筆記。也歡迎直接公眾號私信或者郵箱聯繫我，一定知無不言，言無不盡。

以上皆為個人所思所得，如有錯誤歡迎評論區指正。

歡迎轉載，煩請署名並保留原文鏈接。

聯繫郵箱：[email protected]

更多學習筆記見個人部落格或關注微信公眾號 < 呼延十 >——>呼延