Go實(shí)現(xiàn)雙向鏈表的示例代碼

本文介紹什么是鏈表，常見(jiàn)的鏈表有哪些，然后介紹鏈表這種數(shù)據(jù)結(jié)構(gòu)會(huì)在哪些地方可以用到，以及 Redis 隊(duì)列是底層的實(shí)現(xiàn)，通過(guò)一個(gè)小實(shí)例來(lái)演示 Redis 隊(duì)列有哪些功能，最后通過(guò) Go 實(shí)現(xiàn)一個(gè)雙向鏈表。

目錄

1、鏈表

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

2、redis隊(duì)列

• 2.1 說(shuō)明
• 2.2 應(yīng)用場(chǎng)景
• 2.3 演示

3、Go雙向鏈表

• 3.1 說(shuō)明
• 3.2 實(shí)現(xiàn)

4、總結(jié)

5、參考文獻(xiàn)

• 1、鏈表
• 1.1 說(shuō)明

鏈表（Linked list）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

鏈表有很多種不同的類型：?jiǎn)蜗蜴湵?，雙向鏈表以及循環(huán)鏈表。

優(yōu)勢(shì):

可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)。

劣勢(shì):

由于鏈表增加了節(jié)點(diǎn)指針，空間開(kāi)銷比較大。鏈表一般查找數(shù)據(jù)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開(kāi)始每次訪問(wèn)下一個(gè)節(jié)點(diǎn)，直到訪問(wèn)到需要的位置，查找數(shù)據(jù)比較慢。

用途:

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

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

1.2 單向鏈表

鏈表中最簡(jiǎn)單的一種是單向鏈表，

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

單鏈表有一個(gè)頭節(jié)點(diǎn)head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點(diǎn)有兩個(gè)成員：整型成員（實(shí)際需要保存的數(shù)據(jù)）和指向下一個(gè)結(jié)構(gòu)體類型節(jié)點(diǎn)的指針即下一個(gè)節(jié)點(diǎn)的地址（事實(shí)上，此單鏈表是用于存放整型數(shù)據(jù)的動(dòng)態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對(duì)各節(jié)點(diǎn)的訪問(wèn)需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無(wú)論在表中訪問(wèn)哪個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開(kāi)始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無(wú)后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭?，?xiě)作為NULL。

1.3 循環(huán)鏈表

循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈。

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

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

2、在判斷是否到表尾時(shí)，是判斷該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)，當(dāng)鏈域的值等于表頭指針時(shí)，說(shuō)明已到表尾。而非象單鏈表那樣判斷鏈域的值是否為NULL。

1.4 雙向鏈表

雙向鏈表其實(shí)是單鏈表的改進(jìn)，當(dāng)我們對(duì)單鏈表進(jìn)行操作時(shí)，有時(shí)你要對(duì)某個(gè)結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時(shí)，又必須從表頭開(kāi)始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的。因?yàn)閱捂湵砻總€(gè)結(jié)點(diǎn)只有一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個(gè)既有存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個(gè)雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢？這就是雙向鏈表。

在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個(gè)鏈域，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域（當(dāng)此“連接”為最后一個(gè)“連接”時(shí)，指向空值或者空列表）；一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域（當(dāng)此“連接”為第一個(gè)“連接”時(shí)，指向空值或者空列表）。

2、redis隊(duì)列

2.1 說(shuō)明

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

Redis 列表使用兩種數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn)：雙端列表(linkedlist)、壓縮列表(ziplist)

通過(guò)配置文件中(list-max-ziplist-entries、list-max-ziplist-value)來(lái)選擇是哪種實(shí)現(xiàn)方式

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

redis 鏈表的實(shí)現(xiàn)源碼 redis src/adlist.h

2.2 應(yīng)用場(chǎng)景

消息隊(duì)列，秒殺項(xiàng)目

秒殺項(xiàng)目:

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

2.3 演示

如何通過(guò) Redis 隊(duì)列中防止并發(fā)情況下商品超賣(mài)的情況。

假設(shè)：

網(wǎng)站有三件商品需要賣(mài)，我們將數(shù)據(jù)存入 Redis 隊(duì)列中

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

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

2、 存入以后，查詢數(shù)據(jù)是否符合預(yù)期

# 查看全部元素
LRANGE commodity:queue 0 -1

# 查看隊(duì)列的長(zhǎng)度
LLEN commodity:queue

3、 搶購(gòu)開(kāi)始，獲取商品碼，搶到商品碼的用戶則可以購(gòu)買(mǎi)(由于 Redis 是單線程的，同一個(gè)商品碼只能被取一次

# 出隊(duì)
LPOP commodity:queue

這里了解到 Redis 列表是怎么使用的，下面就用 Go 語(yǔ)言實(shí)現(xiàn)一個(gè)雙向鏈表來(lái)實(shí)現(xiàn)這些功能。

3、Go雙向鏈表

3.1 說(shuō)明

這里只是用 Go 語(yǔ)言實(shí)現(xiàn)一個(gè)雙向鏈表，實(shí)現(xiàn)：查詢鏈表的長(zhǎng)度、鏈表右端插入數(shù)據(jù)、左端取數(shù)據(jù)、取指定區(qū)間的節(jié)點(diǎn)等功能（ 類似于 Redis 列表的中的 RPUSH、LRANGE、LPOP、LLEN功能 ）。

3.2 實(shí)現(xiàn)

節(jié)點(diǎn)定義

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

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

// 鏈表的一個(gè)節(jié)點(diǎn)
type ListNode struct {
  prev *ListNode // 前一個(gè)節(jié)點(diǎn)
  next *ListNode // 后一個(gè)節(jié)點(diǎn)
  value string  // 數(shù)據(jù)
}

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

  return
}

// 當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
func (n *ListNode) Prev() (prev *ListNode) {
  prev = n.prev

  return
}

// 當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
func (n *ListNode) Next() (next *ListNode) {
  next = n.next

  return
}

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

    return
  }
  value = n.value

  return
}

定義一個(gè)鏈表

鏈表為了方便操作，定義一個(gè)結(jié)構(gòu)體，可以直接從表頭、表尾進(jìn)行訪問(wèn)，定義了一個(gè)屬性 len ，直接可以返回鏈表的長(zhǎng)度，直接查詢鏈表的長(zhǎng)度就不用遍歷時(shí)間復(fù)雜度從 O(n) 到 O(1)。

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


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

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

  return
}

// 返回鏈表尾節(jié)點(diǎn)
func (l *List) Tail() (tail *ListNode) {
  tail = l.tail

  return
}

// 返回鏈表長(zhǎng)度
func (l *List) Len() (len int) {
  len = l.len

  return
}

在鏈表的右邊插入一個(gè)元素

// 在鏈表的右邊插入一個(gè)元素
func (l *List) RPush(value string) {

  node := NewListNode(value)

  // 鏈表未空的時(shí)候
  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
}

從鏈表左邊取出一個(gè)節(jié)點(diǎn)

// 從鏈表左邊取出一個(gè)節(jié)點(diǎn)
func (l *List) LPop() (node *ListNode) {

  // 數(shù)據(jù)為空
  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
}

通過(guò)索引查找節(jié)點(diǎn)

通過(guò)索引查找節(jié)點(diǎn)，如果索引是負(fù)數(shù)則從表尾開(kāi)始查找。

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

// 通過(guò)索引查找節(jié)點(diǎn)
// 查不到節(jié)點(diǎn)則返回空
func (l *List) Index(index int) (node *ListNode) {

  // 索引為負(fù)數(shù)則表尾開(kāi)始查找
  if index  0 {
    index = (-index) - 1
    node = l.tail
    for true {
      // 未找到
      if node == nil {

        return
      }

      // 查到數(shù)據(jù)
      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)

  // 轉(zhuǎn)為自然數(shù)
  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ū)間個(gè)數(shù)
  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、總結(jié)

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

5、參考文獻(xiàn)

維基百科 鏈表

github redis

項(xiàng)目地址:go 實(shí)現(xiàn)隊(duì)列

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。