Go 中如何實現各種鏈表？
鏈表是動態內存分配中最常見的數據結構之一。它由一組有限的元素組成，每個元素（節點）至少占用兩塊內存：一塊用于存放數據，另一塊用于存放指向下一個節點的指針。
本文教程將說明在 Go 語言中如何借助指針和結構體類型來實現各種鏈表。
一、Go 中的數據結構
隨機存取存儲器（RAM）可以想象成一張由許多地址單元組成的表格、矩陣或網格。為了在這張表中存放數據，Go 程序員必須先把內存劃分成可定位的結構，并為它們起一個便于識別的名字——變量名。需要注意的是，變量名只是為了方便程序員閱讀；編譯后，名字會被實際的內存引用（例如 0x78BA 這樣的地址）替換。
最簡單的情況下，變量名只對應單個內存單元；復雜時，它可以代表一段連續空間，或是具有行和列的二維區域，也就是數組。數組可通過下標尋址，例如array_name[2][4]表示第二行第四列的元素。
再復雜一些，數據元素之間的結構關系可能并非連續存儲，而是隨機分布，比如用來表示層級關系的樹、分支結構，或含有多重連接的復雜網絡結構。
因此，為了存儲這些結構化關系，Go 開發者必須根據具體需求自行設計內存布局與訪問策略。
二、靜態 vs. 動態內存分配
在內存分配中，有兩個關鍵特性：靜態和動態。
- 靜態數據結構的大小和存儲位置在編譯期就已確定；
- 動態數據結構的大小和位置則未預定義，而是在運行時決定。
舉例來說，當 Go 開發者聲明一個數組時，需要提前給出固定長度，這樣編譯器才能在你使用下標時準確地定位內存地址。而在動態數據結構（例如鏈表）中，下一個數據節點的地址只有在程序執行、節點被創建時才會確定，因此整個結構可在運行期間自由增長或收縮。由于靜態結構存放在連續內存中，元素呈線性排列；動態結構則無此限制。
眾多動態數據結構的基礎——雖然動態分配并不限于此——就是鏈表。鏈表的各數據節點散布在內存的任意位置，通過指針相互連接。因此，一個鏈表節點至少包含兩部分：
- 存放實際數據的元素
- 指向下一節點的鏈接
三、順序存儲與鏈式存儲對比
與順序存儲結構（如數組）不同，鏈式存儲除了保存數據本身，還需要額外的內存來存放指向下一節點的鏈接。這在某些場景下會增加開銷，但鏈式存儲帶來的靈活性通常更具優勢。比如，數組的內存大小在創建時就固定，因此可能出現大量未被利用的空間；而鏈表只有在需要時才創建節點，不會浪費內存。
在鏈表中刪除元素非常容易，而順序存儲往往要移動大量數據才能完成刪除。同樣，鏈表插入元素也很高效。不過，如果要隨機訪問某個位置的元素，順序存儲則更快。
兩種存儲方式各有利弊，Go 程序員應根據具體需求選擇合適的數據結構。
四、鏈表的四種基本形態
鏈表在內存中的組織方式主要有四種：單向（線性）、循環、雙向以及雙向循環。
- 單向（線性）鏈表：只有一個 next 指針指向下一個節點；最后一個節點的 next 為 nil。遍歷時一旦遇到 nil 就表示到達鏈表末尾；
- 循環鏈表：結構與單向鏈表相同，但最后一個節點的 next 指向頭節點，因此尾部再向后訪問就回到起點，可形成“環形”遍歷；
- 雙向鏈表：每個節點同時擁有 prev 與 next 兩個指針，分別指向前驅和后繼節點。這樣即可正向也可反向遍歷，查找元素更靈活；
- 雙向循環鏈表：在雙向鏈表的基礎上，讓尾節點的 next 指向頭節點，頭節點的 prev 指向尾節點，于是可以向前或向后進行環形遍歷。
從單向到雙向、從線性到循環，鏈表的靈活性依次增強。下面的示例將演示在 Go 中實現這幾種鏈表（示例僅涵蓋鏈表的創建與遍歷，以保持簡潔）。
1. 單向鏈表示例
下面是一個在 Go 中創建單向鏈表的示例：
package main
import (
"fmt"
"math/rand"
)
type Node struct {
info interface{}
next *Node
}
type List struct {
head *Node
}
func (l *List) Insert(d interface{}) {
node := &Node{info: d}
if l.head == nil {
l.head = node
return
}
p := l.head
for p.next != nil {
p = p.next
}
p.next = node
}
func Show(l *List) {
for p := l.head; p != nil; p = p.next {
fmt.Printf("-> %v ", p.info)
}
}
func main() {
sl := List{}
for i := 0; i < 5; i++ {
sl.Insert(rand.Intn(100))
}
Show(&sl)
}示例輸出：
-> 81 -> 87 -> 47 -> 59 -> 812. 循環單向鏈表
我們可以輕松地把單向鏈表轉換為循環鏈表。無需修改上述代碼，只需再添加兩個函數：ConvertSinglyToCircular 和 ShowCircular，并在 main 函數中調用它們即可。以下是這兩個函數：
func ConvertSinglyToCircular(l *List) {
if l.head == nil {
return
}
p := l.head
for p.next != nil {
p = p.next
}
p.next = l.head
}
func ShowCircular(l *List) {
p := l.head
for {
fmt.Printf("-> %v ", p.info)
if p.next == l.head {
break
}
p = p.next
}
}注意：雖然假設該鏈表已經是循環的（即 p.next 最終會指回 l.head），但如果 l.head 為 nil（空鏈表），此函數將發生空指針解引用錯誤并崩潰。
現在，在 main 函數中按如下方式調用這兩個函數：
func main() {
sl := List{}
for i := 0; i < 5; i++ {
sl.Insert(rand.Intn(100))
}
ConvertSinglyToCircular(&sl)
ShowCircular(&sl)
}3. 雙向鏈表示例
下面是一個演示如何在 Go 中創建雙向鏈表的代碼示例：
package main
import (
"fmt"
"math/rand"
"time"
)
type Node struct {
info interface{}
prev *Node
next *Node
}
type List struct {
head *Node
tail *Node
}
func (l *List) Insert(d interface{}) {
node := &Node{info: d}
if l.head == nil {
l.head, l.tail = node, node
return
}
l.tail.next = node
node.prev = l.tail
l.tail = node
}
func Show(l *List) {
for p := l.head; p != nil; p = p.next {
fmt.Printf("-> %v ", p.info)
}
}
func ReverseShow(l *List) {
for r := l.tail; r != nil; r = r.prev {
fmt.Printf("-> %v ", r.info)
}
}
func main() {
sl := List{}
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < 10; i++ {
sl.Insert(rnd.Intn(100))
}
Show(&sl)
fmt.Println("\n----------------------------")
ReverseShow(&sl)
}示例輸出：
-> 11 -> 17 -> 56 -> 71 -> 39 -> 44 -> 18 -> 78 -> 25 -> 19
----------------------------
-> 19 -> 25 -> 78 -> 18 -> 44 -> 39 -> 71 -> 56 -> 17 -> 114. 雙向循環鏈表
與循環鏈表類似，雙向循環鏈表也可以很容易地由雙向鏈表轉換而來。我們只需在上述代碼中再添加兩個函數即可。其余代碼保持不變，只需在 main 函數中進行輕微修改，就像在前面的循環鏈表示例中所做的那樣：
func ConvertDoublyToDoublyCircular(l *List) {
if l.head == nil || l.tail == nil {
return
}
l.head.prev = l.tail
l.tail.next = l.head
}
func ShowDoublyCircular(l *List) {
p := l.head
for {
fmt.Printf("-> %v ", p.info)
if p.next == l.head {
break
}
p = p.next
}
}
func ReverseShowDoublyCircular(l *List) {
r := l.tail
for {
fmt.Printf("-> %v ", r.info)
if r.prev == l.tail {
break
}
r = r.prev
}
}main 示例：
func main() {
sl := List{}
rnd := rand.New(rand.NewSource(time.Now().UnixNano()))
for i := 0; i < 10; i++ {
sl.Insert(rnd.Intn(100))
}
ConvertDoublyToDoublyCircular(&sl)
ShowDoublyCircular(&sl)
fmt.Println("\n----------------------------")
ReverseShowDoublyCircular(&sl)
}五、關于在 Go 中實現鏈表的最后思考
正如我們所見，在 Go 語言中實現鏈表相當簡單。鏈式分配可以用來表示各種類型的數據——無論是單個值，還是擁有眾多字段的復雜數據結構。
當配合指針進行順序查找時，訪問速度非常快。與鏈表相關的優化技巧也有不少。與單向鏈表相比，雙向鏈表效率更高，而且能夠在兩個方向上快速遍歷。
