Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（一）：鏈表
鏈表是一種數(shù)據(jù)結(jié)構(gòu)，和數(shù)組不同，鏈表并不需要一塊連續(xù)的內(nèi)存空間，它通過「指針」將一組零散的內(nèi)存塊串聯(lián)起來使用，如圖所示：
一、單鏈表
鏈表有多種類型，最簡單的是單鏈表，單鏈表是最原生的鏈表，其結(jié)構(gòu)如圖所示：
單鏈表中有兩個節(jié)點比較特殊，分別是第一個節(jié)點和最后一個節(jié)點。我們通常把第一個節(jié)點叫作頭節(jié)點，把最后一個結(jié)點叫作尾節(jié)點。
其中，頭節(jié)點用來記錄鏈表的基地址，有了它，我們就可以遍歷得到整條鏈表。而尾節(jié)點特殊的地方是：指針不是指向下一個結(jié)點，而是指向一個空地址 NULL，表示這是鏈表上最后一個節(jié)點。
對于其他普通節(jié)點而言，每個節(jié)點至少使用兩個內(nèi)存空間：一個用于存儲實際數(shù)據(jù)，另一個用于存儲下一個元素的指針，從而形成出一個節(jié)點序列，構(gòu)建鏈表。
對單鏈表而言，理論上來說，插入和刪除節(jié)點的時間復(fù)雜度是 O(1)，查詢節(jié)點的時間復(fù)雜度是 O(n)。
基于 Go 語言實現(xiàn)單鏈表
下面我們基于 Go 語言來實現(xiàn)簡單的單鏈表，并實現(xiàn)添加節(jié)點、遍歷鏈表、查找節(jié)點和獲取鏈表長度等功能：
package main
import (
"fmt"
)
// 定義節(jié)點
type Node struct {
Value int
Next *Node
}
// 初始化頭節(jié)點
var head = new(Node)
// 添加節(jié)點
func addNode(t *Node, v int) int {
if head == nil {
t = &Node{v, nil}
head = t
return 0
}
if v == t.Value {
fmt.Println("節(jié)點已存在:", v)
return -1
}
// 如果當(dāng)前節(jié)點下一個節(jié)點為空
if t.Next == nil {
t.Next = &Node{v, nil}
return -2
}
// 如果當(dāng)前節(jié)點下一個節(jié)點不為空
return addNode(t.Next, v)
}
// 遍歷鏈表
func traverse(t *Node) {
if t == nil {
fmt.Println("-> 空鏈表!")
return
}
for t != nil {
fmt.Printf("%d -> ", t.Value)
t = t.Next
}
fmt.Println()
}
// 查找節(jié)點
func lookupNode(t *Node, v int) bool {
if head == nil {
t = &Node{v, nil}
head = t
return false
}
if v == t.Value {
return true
}
if t.Next == nil {
return false
}
return lookupNode(t.Next, v)
}
// 獲取鏈表長度
func size(t *Node) int {
if t == nil {
fmt.Println("-> 空鏈表!")
return 0
}
i := 0
for t != nil {
i++
t = t.Next
}
return i
}
// 入口函數(shù)
func main() {
fmt.Println(head)
head = nil
// 遍歷鏈表
traverse(head)
// 添加節(jié)點
addNode(head, 1)
addNode(head, -1)
// 再次遍歷
traverse(head)
// 添加更多節(jié)點
addNode(head, 10)
addNode(head, 5)
addNode(head, 45)
// 添加已存在節(jié)點
addNode(head, 5)
// 再次遍歷
traverse(head)
// 查找已存在節(jié)點
if lookupNode(head, 5) {
fmt.Println("該節(jié)點已存在!")
} else {
fmt.Println("該節(jié)點不存在!")
}
// 查找不存在節(jié)點
if lookupNode(head, -100) {
fmt.Println("該節(jié)點已存在!")
} else {
fmt.Println("該節(jié)點不存在!")
}
}
執(zhí)行上述代碼，打印結(jié)果如下：
二、循環(huán)鏈表
還可以在單鏈表的基礎(chǔ)上擴展出循環(huán)鏈表，循環(huán)鏈表和單鏈表的區(qū)別是尾節(jié)點指向了頭節(jié)點，從而首尾相連，有點像貪吃蛇，可用于解決「約瑟夫環(huán)」問題，循環(huán)鏈表的結(jié)構(gòu)如圖所示：
感興趣的同學(xué)可以參考單鏈表自行通過 Go 語言實現(xiàn)循環(huán)鏈表，非常簡單，就是將尾節(jié)點的后驅(qū)節(jié)點指針執(zhí)行頭節(jié)點即可。
三、雙向鏈表
比較常見的鏈表結(jié)構(gòu)還有雙向鏈表，顧名思義，與單鏈表的區(qū)別是雙向鏈表除了有一個指向下一個節(jié)點的指針外，還有一個用于指向上一個節(jié)點的指針，從而實現(xiàn)通過 O(1) 復(fù)雜度找到上一個節(jié)點。正是因為這個指針，使得雙向鏈表在插入、刪除節(jié)點時比單鏈表更高效。
雖然我們前面已經(jīng)提到單鏈表插入、刪除時間復(fù)雜度已經(jīng)是 O(1) 了，但是這只是針對插入、刪除操作本身而言，以刪除為例，刪除某個節(jié)點后，需要將其前驅(qū)節(jié)點的指針指向被刪除節(jié)點的下一個節(jié)點：
這樣，我們還需要獲取其前驅(qū)節(jié)點，在單鏈表中獲取前驅(qū)節(jié)點的時間復(fù)雜度是 O(n)，所以綜合來看單鏈表的刪除、插入操作時間復(fù)雜度也是 O(n)，而雙向鏈表則不然，它有一個指針指向上一個節(jié)點，所以其插入和刪除時間復(fù)雜度才是真正的 O(1)：
此外，對于有序鏈表而言，雙向鏈表的查詢效率顯然也要高于單鏈表，不過更優(yōu)的時間復(fù)雜度是靠更差的空間復(fù)雜度換取的，雙向鏈表始終需要單鏈表的兩倍空間，不過正如我們之前說的，在 Web 應(yīng)用中，時間效率優(yōu)先級更高，所以我們通常都是空間換時間來提高性能，Java 的 LinkedHashMap 底層就用到了雙向鏈表，此外在日常應(yīng)用中，音樂軟件的播放列表也是一個典型的雙向鏈表（支持在上一首和下一首之間進(jìn)行切換）。
雙向鏈表的結(jié)構(gòu)如圖所示：
基于 Go 語言實現(xiàn)雙向鏈表
下面我們來看看如何基于 Go 語言實現(xiàn)雙向鏈表，和單鏈表相比，雙向鏈表需要多維護(hù)一個前驅(qū)節(jié)點指針，以及支持反向遍歷：
package main
import (
"fmt"
)
// 定義節(jié)點
type Node struct {
Value int
Previous *Node
Next *Node
}
// 添加節(jié)點
func addNode(t *Node, v int) int {
if head == nil {
t = &Node{v, nil, nil}
head = t
return 0
}
if v == t.Value {
fmt.Println("節(jié)點已存在:", v)
return -1
}
// 如果當(dāng)前節(jié)點下一個節(jié)點為空
if t.Next == nil {
// 與單鏈表不同的是每個節(jié)點還要維護(hù)前驅(qū)節(jié)點指針
temp := t
t.Next = &Node{v, temp, nil}
return -2
}
// 如果當(dāng)前節(jié)點下一個節(jié)點不為空
return addNode(t.Next, v)
}
// 遍歷鏈表
func traverse(t *Node) {
if t == nil {
fmt.Println("-> 空鏈表!")
return
}
for t != nil {
fmt.Printf("%d -> ", t.Value)
t = t.Next
}
fmt.Println()
}
// 反向遍歷鏈表
func reverse(t *Node) {
if t == nil {
fmt.Println("-> 空鏈表!")
return
}
temp := t
for t != nil {
temp = t
t = t.Next
}
for temp.Previous != nil {
fmt.Printf("%d -> ", temp.Value)
temp = temp.Previous
}
fmt.Printf("%d -> ", temp.Value)
fmt.Println()
}
// 獲取鏈表長度
func size(t *Node) int {
if t == nil {
fmt.Println("-> 空鏈表!")
return 0
}
n := 0
for t != nil {
n++
t = t.Next
}
return n
}
// 查找節(jié)點
func lookupNode(t *Node, v int) bool {
if head == nil {
return false
}
if v == t.Value {
return true
}
if t.Next == nil {
return false
}
return lookupNode(t.Next, v)
}
// 初始化頭節(jié)點
var head = new(Node)
func main() {
fmt.Println(head)
head = nil
// 遍歷鏈表
traverse(head)
// 新增節(jié)點
addNode(head, 1)
// 再次遍歷
traverse(head)
// 繼續(xù)添加節(jié)點
addNode(head, 10)
addNode(head, 5)
addNode(head, 100)
// 再次遍歷
traverse(head)
// 添加已存在節(jié)點
addNode(head, 100)
fmt.Println("鏈表長度:", size(head))
// 再次遍歷
traverse(head)
// 反向遍歷
reverse(head)
// 查找已存在節(jié)點
if lookupNode(head, 5) {
fmt.Println("該節(jié)點已存在!")
} else {
fmt.Println("該節(jié)點不存在!")
}
}
運行上述代碼，打印結(jié)果如下：
四、雙向循環(huán)鏈表
最后，我們要介紹的是結(jié)合循環(huán)鏈表和雙向鏈表為一體的雙向循環(huán)鏈表：
感興趣的同學(xué)可以參考雙向鏈表自行基于 Go 語言實現(xiàn)雙向循環(huán)鏈表，其實就是將雙向鏈表的首尾通過指針連接起來，對于支持循環(huán)播放的音樂列表其實就是個雙向循環(huán)鏈表結(jié)構(gòu)。
（本文完）
推薦閱讀