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)
項目地址:go 實現(xiàn)隊列
