主頁 > 知識庫 > Go實現(xiàn)雙向鏈表的示例代碼

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

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

1、鏈表

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

2、redis隊列

2.1 說明
2.2 應(yīng)用場景
2.3 演示

3、Go雙向鏈表

3.1 說明
3.2 實現(xiàn)

4、總結(jié)

5、參考文獻(xiàn)

1、鏈表
1.1 說明

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

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

優(yōu)勢:

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

劣勢:

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

用途:

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

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

1.2 單向鏈表

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

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

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

1.3 循環(huán)鏈表

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

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

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

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

1.4 雙向鏈表

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

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

2、redis隊列

2.1 說明

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

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

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

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

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

2.2 應(yīng)用場景

消息隊列，秒殺項目

秒殺項目:

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

2.3 演示

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

假設(shè)：

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

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

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

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

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

# 查看隊列的長度
LLEN commodity:queue

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

# 出隊
LPOP commodity:queue

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

3、Go雙向鏈表

3.1 說明

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

3.2 實現(xiàn)

節(jié)點定義

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

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

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

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

  return
}

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

  return
}

// 當(dāng)前節(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
}

定義一個鏈表

鏈表為了方便操作，定義一個結(jié)構(gòu)體，可以直接從表頭、表尾進(jìn)行訪問，定義了一個屬性 len ，直接可以返回鏈表的長度，直接查詢鏈表的長度就不用遍歷時間復(fù)雜度從 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) {

  // 數(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
}

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

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

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

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

  // 索引為負(fù)數(shù)則表尾開始查找
  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ū)間個數(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)用場景(Redis 列表使用的是鏈表作為底層實現(xiàn))，最后用 Go 實現(xiàn)了雙向鏈表，演示了鏈表在 Go 語言中是怎么使用的，大家可以在項目中更具實際的情況去使用。

5、參考文獻(xiàn)

維基百科鏈表

github redis

項目地址:go 實現(xiàn)隊列

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

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

您可能感興趣的文章:

詳解go語言單鏈表及其常用方法的實現(xiàn)
python/golang 刪除鏈表中的元素
python/golang實現(xiàn)循環(huán)鏈表的示例代碼
golang雙鏈表的實現(xiàn)代碼示例
Go語言單鏈表實現(xiàn)方法
go實現(xiàn)反轉(zhuǎn)鏈表

標(biāo)簽：銅川湖南崇左蘭州仙桃衡水黃山湘潭

巨人網(wǎng)絡(luò)通訊聲明：本文標(biāo)題《Go實現(xiàn)雙向鏈表的示例代碼》，本文關(guān)鍵詞；如發(fā)現(xiàn)本文內(nèi)容存在版權(quán)問題，煩請?zhí)峁┫嚓P(guān)信息告之我們，我們將及時溝通與處理。本站內(nèi)容系統(tǒng)采集于網(wǎng)絡(luò)，涉及言論、版權(quán)與本站無關(guān)。