欧美一区二区,精品视频成人,麻豆精品一区二区

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

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

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

1、鏈表

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

2、redis隊(duì)列

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

3、Go雙向鏈表

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

4、總結(jié)

5、參考文獻(xiàn)

1、鏈表
1.1 說明

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

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

優(yōu)勢:

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

劣勢:

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

用途:

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

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

1.2 單向鏈表

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

一個(gè)單向鏈表的節(jié)點(diǎn)被分成兩個(gè)部分。它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息，第二個(gè)部分存儲下一個(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ù)的動態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對各節(jié)點(diǎn)的訪問需從鏈表的頭找起，后續(xù)節(jié)點(diǎn)的地址由當(dāng)前節(jié)點(diǎn)給出。無論在表中訪問哪個(gè)節(jié)點(diǎn)，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點(diǎn)由于無后續(xù)節(jié)點(diǎn)，其指針域?yàn)榭眨瑢懽鳛镹ULL。

1.3 循環(huán)鏈表

循環(huán)鏈表是與單向鏈表一樣，是一種鏈?zhǔn)降拇鎯Y(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í)，說明已到表尾。而非象單鏈表那樣判斷鏈域的值是否為NULL。

1.4 雙向鏈表

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

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

2、redis隊(duì)列

2.1 說明

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

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

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

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

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

2.2 應(yīng)用場景

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

秒殺項(xiàng)目:

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

2.3 演示

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

假設(shè)：

網(wǎng)站有三件商品需要賣，我們將數(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ì)列的長度
LLEN commodity:queue

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

# 出隊(duì)
LPOP commodity:queue

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

3、Go雙向鏈表

3.1 說明

這里只是用 Go 語言實(shí)現(xiàn)一個(gè)雙向鏈表，實(shí)現(xiàn)：查詢鏈表的長度、鏈表右端插入數(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)行訪問，定義了一個(gè)屬性 len ，直接可以返回鏈表的長度，直接查詢鏈表的長度就不用遍歷時(shí)間復(fù)雜度從 O(n) 到 O(1)。

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


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

// 返回鏈表長度
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
}

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

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

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

// 通過索引查找節(jié)點(diǎn)
// 查不到節(jié)點(diǎn)則返回空
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ū)間個(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)用場景(Redis 列表使用的是鏈表作為底層實(shí)現(xiàn))，最后用 Go 實(shí)現(xiàn)了雙向鏈表，演示了鏈表在 Go 語言中是怎么使用的，大家可以在項(xiàng)目中更具實(shí)際的情況去使用。

5、參考文獻(xiàn)

維基百科鏈表

github redis

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

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

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

您可能感興趣的文章:

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

標(biāo)簽：保定吐魯番曲靖德宏許昌常州貴州東營

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