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