• 前言
• 定義
• 優劣
  • 雙向鏈表
  • 無環鏈表
  • 帶有頭指針和尾指針
  • 帶有長度計數器
• 總結
• 參考文章
• 聯系我

前言

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 的設計與實現（第二版）》

完。

聯系我

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

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

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

聯系郵箱：huyanshi2580@gmail.com

更多學習筆記見個人博客或關注微信公眾號 < 呼延十 >------>呼延十

總結

以上是生活随笔為你收集整理的设某链表中最常用的操作是在链表的尾部_Redis系列(二)底层数据结构之双端链表...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。