本文介紹什么是鏈表，常見的鏈表有哪些，然后介紹鏈表這種數(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隊列
3、Go雙向鏈表
4、總結(jié)
5、參考文獻
鏈表（Linked list）是一種常見的基礎數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應的時間復雜度分別是O(logn)和O(1)。
鏈表有很多種不同的類型：單向鏈表，雙向鏈表以及循環(huán)鏈表。
優(yōu)勢:
可以克服數(shù)組鏈表需要預先知道數(shù)據(jù)大小的缺點，鏈表結(jié)構(gòu)可以充分利用計算機內(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é)點的地址由當前節(jié)點給出。無論在表中訪問哪個節(jié)點，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點，其指針域為空，寫作為NULL。
1.3 循環(huán)鏈表
循環(huán)鏈表是與單向鏈表一樣，是一種鏈式的存儲結(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é)點，當鏈域的值等于表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域的值是否為NULL。
1.4 雙向鏈表
雙向鏈表其實是單鏈表的改進，當我們對單鏈表進行操作時，有時你要對某個結(jié)點的直接前驅(qū)進行操作時，又必須從表頭開始查找。這是由單鏈表結(jié)點的結(jié)構(gòu)所限制的。因為單鏈表每個結(jié)點只有一個存儲直接后繼結(jié)點地址的鏈域，那么能不能定義一個既有存儲直接后繼結(jié)點地址的鏈域，又有存儲直接前驅(qū)結(jié)點地址的鏈域的這樣一個雙鏈域結(jié)點結(jié)構(gòu)呢？這就是雙向鏈表。
在雙向鏈表中，結(jié)點除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結(jié)點地址，一般稱之為右鏈域（當此“連接”為最后一個“連接”時，指向空值或者空列表）；一個存儲直接前驅(qū)結(jié)點地址，一般稱之為左鏈域（當此“連接”為第一個“連接”時，指向空值或者空列表）。
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 應用場景
消息隊列，秒殺項目
秒殺項目:
提前將需要的商品碼信息存入 Redis 隊列，在搶購的時候每個用戶都從 Redis 隊列中取商品碼，由于 Redis 是單線程的，同時只能有一個商品碼被取出，取到商品碼的用戶為購買成功，而且 Redis 性能比較高，能抗住較大的用戶壓力。
2.3 演示
如何通過 Redis 隊列中防止并發(fā)情況下商品超賣的情況。
假設：
網(wǎng)站有三件商品需要賣，我們將數(shù)據(jù)存入 Redis 隊列中
1、 將三個商品碼(10001、10002、10003)存入 Redis 隊列中
# 存入商品
RPUSH commodity:queue 10001 10002 10003
2、 存入以后，查詢數(shù)據(jù)是否符合預期
# 查看全部元素
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
}
// 當前節(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
}
定義一個鏈表
鏈表為了方便操作，定義一個結(jié)構(gòu)體，可以直接從表頭、表尾進行訪問，定義了一個屬性 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) {
// 數(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é)點，如果索引是負數(shù)則從表尾開始查找。
自然數(shù)和負數(shù)索引分別通過兩種方式查找節(jié)點，找到指定索引或者是鏈表全部查找完則查找完成。
// 通過索引查找節(jié)點
// 查不到節(jié)點則返回空
func (l *List) Index(index int) (node *ListNode) {
// 索引為負數(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)鏈表)，也介紹了鏈表的應用場景(Redis 列表使用的是鏈表作為底層實現(xiàn))，最后用 Go 實現(xiàn)了雙向鏈表，演示了鏈表在 Go 語言中是怎么使用的，大家可以在項目中更具實際的情況去使用。
5、參考文獻
維基百科 鏈表
github redis
項目地址:go 實現(xiàn)隊列
https://github.com/link1st/link1st/tree/master/linked
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
您可能感興趣的文章:- 詳解go語言單鏈表及其常用方法的實現(xiàn)
- python/golang 刪除鏈表中的元素
- python/golang實現(xiàn)循環(huán)鏈表的示例代碼
- golang雙鏈表的實現(xiàn)代碼示例
- Go語言單鏈表實現(xiàn)方法
- go實現(xiàn)反轉(zhuǎn)鏈表
