Go實現雙向鏈表 | Redis 隊列的實現

2019 年 10 月 8 日
筆記

本文介紹什麼是鏈表，常見的鏈表有哪些，然後介紹鏈表這種數據結構會在哪些地方可以用到，以及 Redis 隊列是底層的實現，通過一個小實例來演示 Redis 隊列有哪些功能，最後通過 Go 實現一個雙向鏈表。

1、鏈表

1.1 說明

鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是並不會按線性的順序存儲數據，而是在每一個節點裡存到下一個節點的指針(Pointer)。由於不必須按順序存儲，鏈表在插入的時候可以達到O(1)的複雜度，比另一種線性表順序錶快得多，但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間，而順序表相應的時間複雜度分別是O(logn)和O(1)。

鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環鏈表。

優勢:

可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。鏈表允許插入和移除表上任意位置上的節點。

劣勢:

由於鏈表增加了節點指針，空間開銷比較大。鏈表一般查找數據的時候需要從第一個節點開始每次訪問下一個節點，直到訪問到需要的位置，查找數據比較慢。

用途:

常用於組織檢索較少，而刪除、添加、遍歷較多的數據。

如：文件系統、LRU cache、Redis 列表、記憶體管理等。

1.2 單向鏈表

鏈表中最簡單的一種是單向鏈表，

一個單向鏈表的節點被分成兩個部分。它包含兩個域，一個資訊域和一個指針域。第一個部分保存或者顯示關於節點的資訊，第二個部分存儲下一個節點的地址，而最後一個節點則指向一個空值。單向鏈表只可向一個方向遍歷。

單鏈表有一個頭節點head，指向鏈表在記憶體的首地址。鏈表中的每一個節點的數據類型為結構體類型，節點有兩個成員：整型成員（實際需要保存的數據）和指向下一個結構體類型節點的指針即下一個節點的地址（事實上，此單鏈表是用於存放整型數據的動態數組）。鏈表按此結構對各節點的訪問需從鏈表的頭找起，後續節點的地址由當前節點給出。無論在表中訪問哪個節點，都需要從鏈表的頭開始，順序向後查找。鏈表的尾節點由於無後續節點，其指針域為空，寫作為NULL。

1.3 循環鏈表

循環鏈表是與單向鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。

循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點：

1、在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是像單鏈表那樣置為NULL。

2、在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域的值等於表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域的值是否為NULL。

1.4 雙向鏈表

雙向鏈表其實是單鏈表的改進，當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接後繼結點地址的鏈域，那麼能不能定義一個既有存儲直接後繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。

在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接後繼結點地址，一般稱之為右鏈域（當此「連接」為最後一個「連接」時，指向空值或者空列表）；一個存儲直接前驅結點地址，一般稱之為左鏈域（當此「連接」為第一個「連接」時，指向空值或者空列表）。

2、redis隊列

2.1 說明

Redis 列表是簡單的字元串列表，按照插入順序排序。你可以添加一個元素到列表的頭部（左邊）或者尾部（右邊）

Redis 列表使用兩種數據結構作為底層實現：雙端列表(linkedlist)、壓縮列表(ziplist)

通過配置文件中(list-max-ziplist-entries、list-max-ziplist-value)來選擇是哪種實現方式

在數據量比較少的時候，使用雙端鏈表和壓縮列表性能差異不大，但是使用壓縮列表更能節約記憶體空間

redis 鏈表的實現源碼 redis src/adlist.h

2.2 應用場景

消息隊列，秒殺項目

秒殺項目:

提前將需要的商品碼資訊存入 Redis 隊列，在搶購的時候每個用戶都從 Redis 隊列中取商品碼，由於 Redis 是單執行緒的，同時只能有一個商品碼被取出，取到商品碼的用戶為購買成功，而且 Redis 性能比較高，能抗住較大的用戶壓力。

2.3 演示

如何通過 Redis 隊列中防止並發情況下商品超賣的情況。

假設：

網站有三件商品需要賣，我們將數據存入 Redis 隊列中

1、將三個商品碼(10001、10002、10003)存入 Redis 隊列中

# 存入商品  RPUSH commodity:queue 10001 10002 10003

2、存入以後，查詢數據是否符合預期

# 查看全部元素  LRANGE commodity:queue 0 -1    # 查看隊列的長度  LLEN commodity:queue

3、搶購開始，獲取商品碼，搶到商品碼的用戶則可以購買(由於 Redis 是單執行緒的，同一個商品碼只能被取一次

)

# 出隊  LPOP commodity:queue

這裡了解到 Redis 列表是怎麼使用的，下面就用 Go 語言實現一個雙向鏈表來實現這些功能。

3、Go雙向鏈表

3.1 說明

這裡只是用 Go 語言實現一個雙向鏈表，實現：查詢鏈表的長度、鏈表右端插入數據、左端取數據、取指定區間的節點等功能（類似於 Redis 列表的中的 RPUSH、LRANGE、LPOP、LLEN功能）。

3.2 實現

節點定義

雙向鏈表有兩個指針，分別指向前一個節點和後一個節點

鏈表表頭 prev 的指針為空，鏈表表尾 next 的指針為空

// 鏈表的一個節點  type ListNode struct {      prev  *ListNode // 前一個節點      next  *ListNode // 後一個節點      value string    // 數據  }    // 創建一個節點  func NewListNode(value string) (listNode *ListNode) {      listNode = &ListNode{          value: value,      }        return  }    // 當前節點的前一個節點  func (n *ListNode) Prev() (prev *ListNode) {      prev = n.prev        return  }    // 當前節點的前一個節點  func (n *ListNode) Next() (next *ListNode) {      next = n.next        return  }    // 獲取節點的值  func (n *ListNode) GetValue() (value string) {      if n == nil {            return      }      value = n.value        return  }

定義一個鏈表

鏈表為了方便操作，定義一個結構體，可以直接從表頭、表尾進行訪問，定義了一個屬性 len ，直接可以返回鏈表的長度，直接查詢鏈表的長度就不用遍歷時間複雜度從 O(n) 到 O(1)。

// 鏈表  type List struct {      head *ListNode // 表頭節點      tail *ListNode // 表尾節點      len  int       // 鏈表的長度  }      // 創建一個空鏈表  func NewList() (list *List) {      list = &List{      }      return  }    // 返回鏈表頭節點  func (l *List) Head() (head *ListNode) {      head = l.head        return  }    // 返回鏈表尾節點  func (l *List) Tail() (tail *ListNode) {      tail = l.tail        return  }    // 返回鏈表長度  func (l *List) Len() (len int) {      len = l.len        return  }

在鏈表的右邊插入一個元素

// 在鏈表的右邊插入一個元素  func (l *List) RPush(value string) {        node := NewListNode(value)        // 鏈表未空的時候      if l.Len() == 0 {          l.head = node          l.tail = node      } else {          tail := l.tail          tail.next = node          node.prev = tail            l.tail = node      }        l.len = l.len + 1        return  }

從鏈表左邊取出一個節點

// 從鏈表左邊取出一個節點  func (l *List) LPop() (node *ListNode) {        // 數據為空      if l.len == 0 {            return      }        node = l.head        if node.next == nil {          // 鏈表未空          l.head = nil          l.tail = nil      } else {          l.head = node.next      }      l.len = l.len - 1        return  }

通過索引查找節點

通過索引查找節點，如果索引是負數則從表尾開始查找。

自然數和負數索引分別通過兩種方式查找節點，找到指定索引或者是鏈表全部查找完則查找完成。

// 通過索引查找節點  // 查不到節點則返回空  func (l *List) Index(index int) (node *ListNode) {        // 索引為負數則表尾開始查找      if index < 0 {          index = (-index) - 1          node = l.tail          for true {              // 未找到              if node == nil {                    return              }                // 查到數據              if index == 0 {                    return              }                node = node.prev              index--          }      } else {          node = l.head          for ; index > 0 && node != nil; index-- {              node = node.next          }      }        return  }

返回指定區間的元素

// 返回指定區間的元素  func (l *List) Range(start, stop int) (nodes []*ListNode) {      nodes = make([]*ListNode, 0)        // 轉為自然數      if start < 0 {          start = l.len + start          if start < 0 {              start = 0          }      }        if stop < 0 {          stop = l.len + stop          if stop < 0 {              stop = 0          }      }        // 區間個數      rangeLen := stop - start + 1      if rangeLen < 0 {            return      }        startNode := l.Index(start)      for i := 0; i < rangeLen; i++ {          if startNode == nil {              break          }            nodes = append(nodes, startNode)          startNode = startNode.next      }        return  }

4、總結

到這裡關於鏈表的使用已經結束，介紹鏈表是有哪些(單向鏈表，雙向鏈表以及循環鏈表)，也介紹了鏈表的應用場景(Redis 列表使用的是鏈表作為底層實現)，最後用 Go 實現了雙向鏈表，演示了鏈表在 Go 語言中是怎麼使用的，大家可以在項目中更具實際的情況去使用。

5、參考文獻

維基百科鏈表

github redis

項目地址:go 實現隊列

https://github.com/link1st/link1st/tree/master/linked