Go實現雙向鏈表的示例代碼

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

目錄

1、鏈表

• 1.1 說明
• 1.2 單向鏈表
• 1.3 循環(huán)鏈表
• 1.4 雙向鏈表

2、redis隊列

• 2.1 說明
• 2.2 應用場景
• 2.3 演示

3、Go雙向鏈表

• 3.1 說明
• 3.2 實現

4、總結

5、參考文獻

• 1、鏈表
• 1.1 說明

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

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

優(yōu)勢:

可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態(tài)管理。鏈表允許插入和移除表上任意位置上的節(jié)點。

劣勢:

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

用途:

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

如：文件系統(tǒng)、LRU cache、Redis 列表、內存管理等。

1.2 單向鏈表

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

一個單向鏈表的節(jié)點被分成兩個部分。它包含兩個域，一個信息域和一個指針域。第一個部分保存或者顯示關于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址，而最后一個節(jié)點則指向一個空值。單向鏈表只可向一個方向遍歷。

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

1.3 循環(huán)鏈表

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

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

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

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

1.4 雙向鏈表

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

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

2、redis隊列

2.1 說明

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

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

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

在數據量比較少的時候，使用雙端鏈表和壓縮列表性能差異不大，但是使用壓縮列表更能節(jié)約內存空間

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

2.2 應用場景

消息隊列，秒殺項目

秒殺項目:

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

2.3 演示

如何通過 Redis 隊列中防止并發(fā)情況下商品超賣的情況。

假設：

網站有三件商品需要賣，我們將數據存入 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 語言實現一個雙向鏈表，實現：查詢鏈表的長度、鏈表右端插入數據、左端取數據、取指定區(qū)間的節(jié)點等功能（ 類似于 Redis 列表的中的 RPUSH、LRANGE、LPOP、LLEN功能 ）。

3.2 實現

節(jié)點定義

雙向鏈表有兩個指針，分別指向前一個節(jié)點和后一個節(jié)點

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

// 鏈表的一個節(jié)點
type ListNode struct {
  prev *ListNode // 前一個節(jié)點
  next *ListNode // 后一個節(jié)點
  value string  // 數據
}

// 創(chuàng)建一個節(jié)點
func NewListNode(value string) (listNode *ListNode) {
  listNode = &ListNode{
    value: value,
  }

  return
}

// 當前節(jié)點的前一個節(jié)點
func (n *ListNode) Prev() (prev *ListNode) {
  prev = n.prev

  return
}

// 當前節(jié)點的前一個節(jié)點
func (n *ListNode) Next() (next *ListNode) {
  next = n.next

  return
}

// 獲取節(jié)點的值
func (n *ListNode) GetValue() (value string) {
  if n == nil {

    return
  }
  value = n.value

  return
}

定義一個鏈表

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

// 鏈表
type List struct {
  head *ListNode // 表頭節(jié)點
  tail *ListNode // 表尾節(jié)點
  len int    // 鏈表的長度
}


// 創(chuàng)建一個空鏈表
func NewList() (list *List) {
  list = &List{
  }
  return
}

// 返回鏈表頭節(jié)點
func (l *List) Head() (head *ListNode) {
  head = l.head

  return
}

// 返回鏈表尾節(jié)點
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
}

從鏈表左邊取出一個節(jié)點

// 從鏈表左邊取出一個節(jié)點
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
}

通過索引查找節(jié)點

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

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

// 通過索引查找節(jié)點
// 查不到節(jié)點則返回空
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
}

返回指定區(qū)間的元素

// 返回指定區(qū)間的元素
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
    }
  }

  // 區(qū)間個數
  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、總結

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

5、參考文獻

維基百科 鏈表

github redis

項目地址:go 實現隊列

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

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。