本文介紹什么是鏈表，常見的鏈表有哪些，然后介紹鏈表這種數(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)鏈表的運(yùn)算與單鏈表的運(yù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í)有所幫助，也希望大家多多支持腳本之家。

最新評論