如何在 Go 中實現各種類型的鏈表？

鏈表是動態內存分配中最常見的數據結構之一。它由一組有限的元素組成，每個元素（節點）至少占用兩塊內存：一塊用于存放數據，另一塊用于存放指向下一個節點的指針。本文教程將說明在 Go 語言中如何借助指針和結構體類型來實現各種鏈表

Go 中的數據結構

隨機存取存儲器（RAM）可以想象成一張由許多地址單元組成的表格、矩陣或網格。為了在這張表中存放數據，Go 程序員必須先把內存劃分成可定位的結構，并為它們起一個便于識別的名字——變量名。需要注意的是，變量名只是為了方便程序員閱讀；編譯后，名字會被實際的內存引用（例如 0x78BA 這樣的地址）替換

最簡單的情況下，變量名只對應單個內存單元；復雜時，它可以代表一段連續空間，或是具有行和列的二維區域，也就是數組。數組可通過下標尋址，例如array_name[2][4]表示第二行第四列的元素。

再復雜一些，數據元素之間的結構關系可能并非連續存儲，而是隨機分布，比如用來表示層級關系的樹、分支結構，或含有多重連接的復雜網絡結構。

因此，為了存儲這些結構化關系，Go 開發者必須根據具體需求自行設計內存布局與訪問策略。

靜態 vs. 動態內存分配

在內存分配中，有兩個關鍵特性：靜態和動態。

靜態數據結構的大小和存儲位置在編譯期就已確定；
動態數據結構的大小和位置則未預定義，而是在運行時決定。

舉例來說，當 Go 開發者聲明一個數組時，需要提前給出固定長度，這樣編譯器才能在你使用下標時準確地定位內存地址。而在動態數據結構（例如鏈表）中，下一個數據節點的地址只有在程序執行、節點被創建時才會確定，因此整個結構可在運行期間自由增長或收縮。由于靜態結構存放在連續內存中，元素呈線性排列；動態結構則無此限制。

眾多動態數據結構的基礎——雖然動態分配并不限于此——就是鏈表。鏈表的各數據節點散布在內存的任意位置，通過指針相互連接。因此，一個鏈表節點至少包含兩部分：

存放實際數據的元素
指向下一節點的鏈接

順序存儲與鏈式存儲對比

與順序存儲結構（如數組）不同，鏈式存儲除了保存數據本身，還需要額外的內存來存放指向下一節點的鏈接。這在某些場景下會增加開銷，但鏈式存儲帶來的靈活性通常更具優勢。比如，數組的內存大小在創建時就固定，因此可能出現大量未被利用的空間；而鏈表只有在需要時才創建節點，不會浪費內存。

在鏈表中刪除元素非常容易，而順序存儲往往要移動大量數據才能完成刪除。同樣，鏈表插入元素也很高效。不過，如果要隨機訪問某個位置的元素，順序存儲則更快。

兩種存儲方式各有利弊，Go 程序員應根據具體需求選擇合適的數據結構。

鏈表的 4 種基本形態

鏈表在內存中的組織方式主要有四種：單向（線性）、循環、雙向以及雙向循環。

單向（線性）鏈表：只有一個 next 指針指向下一個節點；最后一個節點的 next 為 nil。遍歷時一旦遇到 nil 就表示到達鏈表末尾；
循環鏈表：結構與單向鏈表相同，但最后一個節點的 next 指向頭節點，因此尾部再向后訪問就回到起點，可形成“環形”遍歷；
雙向鏈表：每個節點同時擁有 prev 與 next 兩個指針，分別指向前驅和后繼節點。這樣即可正向也可反向遍歷，查找元素更靈活；
雙向循環鏈表：在雙向鏈表的基礎上，讓尾節點的 next 指向頭節點，頭節點的 prev 指向尾節點，于是可以向前或向后進行環形遍歷。

從單向到雙向、從線性到循環，鏈表的靈活性依次增強。下面的示例將演示在 Go 中實現這幾種鏈表（示例僅涵蓋鏈表的創建與遍歷，以保持簡潔）。

一、單向鏈表示例

下面是一個在 Go 中創建單向鏈表的示例：

package mainimport ("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 = nodereturn}p := l.headfor 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 -> 81

二、循環單向鏈表

我們可以輕松地把單向鏈表轉換為循環鏈表。無需修改上述代碼，只需再添加兩個函數：ConvertSinglyToCircular 和 ShowCircular，并在 main 函數中調用它們即可。以下是這兩個函數：

func ConvertSinglyToCircular(l *List) {if l.head == nil {return}p := l.headfor p.next != nil {p = p.next}p.next = l.head
}func ShowCircular(l *List) {p := l.headfor {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)
}

三、雙向鏈表示例

下面是一個演示如何在 Go 中創建雙向鏈表的代碼示例：

package mainimport ("fmt""math/rand""time"
)type Node struct {info interface{}prev *Nodenext *Node
}type List struct {head *Nodetail *Node
}func (l *List) Insert(d interface{}) {node := &Node{info: d}if l.head == nil {l.head, l.tail = node, nodereturn}l.tail.next = nodenode.prev = l.taill.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 -> 11

四、雙向循環鏈表

與循環鏈表類似，雙向循環鏈表也可以很容易地由雙向鏈表轉換而來。我們只需在上述代碼中再添加兩個函數即可。其余代碼保持不變，只需在 main 函數中進行輕微修改，就像在前面的循環鏈表示例中所做的那樣：

func ConvertDoublyToDoublyCircular(l *List) {if l.head == nil || l.tail == nil {return}l.head.prev = l.taill.tail.next = l.head
}func ShowDoublyCircular(l *List) {p := l.headfor {fmt.Printf("-> %v ", p.info)if p.next == l.head {break}p = p.next}
}func ReverseShowDoublyCircular(l *List) {r := l.tailfor {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 語言中實現鏈表相當簡單。鏈式分配可以用來表示各種類型的數據——無論是單個值，還是擁有眾多字段的復雜數據結構。

當配合指針進行順序查找時，訪問速度非常快。與鏈表相關的優化技巧也有不少。與單向鏈表相比，雙向鏈表效率更高，而且能夠在兩個方向上快速遍歷。

知識星球：云原生AI實戰營。10+ 高質量體系課（ Go、云原生、AI Infra）、15+ 實戰項目，P8 技術專家助你提高技術天花板，入大廠拿高薪；
公眾號：令飛編程，分享 Go、云原生、AI Infra 相關技術。回復「資料」免費下載 Go、云原生、AI 等學習資料；
嗶哩嗶哩：令飛編程，分享技術、職場、面經等，并有免費直播課「云原生AI高新就業課」，大廠級項目實戰到大廠面試通關；

例行海報