Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學(xué)習教程
雙鏈表
雙鏈表 （Doubly Linked List），每個節(jié)點持有一個指向列表前一個元素的指針，以及指向下一個元素的指針。
雙向鏈表的節(jié)點中包含 3 個字段：
- 數(shù)據(jù)域
Value - 一個
Next指針指向雙鏈表中的下一個節(jié)點 - 一個
Prev指針，指向雙鏈表中的前一個節(jié)點
結(jié)構(gòu)體如下：
type Node struct {
Prev *Node
Value int
Next *Node
}
實際應(yīng)用： 音樂播放器的播放列表，使用雙向鏈表可以快速訪問上一個歌曲和下一首歌曲。
創(chuàng)建節(jié)點
func CreateNewNode(value int) *Node {
var node Node
node.Next = nil
node.Value = value
node.Prev = nil
return &node
}
雙鏈表遍歷
雙向鏈表的遍歷與單鏈表的遍歷類似。我們必須首先檢查一個條件：鏈表是否為空。這有助于將開始指針設(shè)置在適當?shù)奈恢?。之后我們訪問每個節(jié)點直到結(jié)束。
func TraverseDoublyLinkedList(head *Node) {
if head == nil {
fmt.Println("-> Empty list!")
return
}
for head != nil {
if head.Next != nil {
fmt.Printf("%d <-> ", head.Value)
} else {
fmt.Printf("%d ", head.Value)
}
head = head.Next
}
fmt.Println()
}
為了測試，我們的完整代碼：
package main
import "fmt"
type Node struct {
Prev *Node
Value int
Next *Node
}
func CreateNewNode(value int) *Node {
var node Node
node.Next = nil
node.Value = value
node.Prev = nil
return &node
}
func TraverseDoublyLinkedList(head *Node) {
if head == nil {
fmt.Println("-> Empty list!")
return
}
for head != nil {
if head.Next != nil {
fmt.Printf("%d <-> ", head.Value)
} else {
fmt.Printf("%d ", head.Value)
}
head = head.Next
}
fmt.Println()
}
func main() {
// 1 <-> 2 <-> 3 <-> 4 <-> 5
head := CreateNewNode(1)
node_2 := CreateNewNode(2)
node_3 := CreateNewNode(3)
node_4 := CreateNewNode(4)
node_5 := CreateNewNode(5)
head.Next = node_2
node_2.Prev = head
node_2.Next = node_3
node_3.Prev = node_2
node_3.Next = node_4
node_4.Prev = node_3
node_4.Next = node_5
TraverseDoublyLinkedList(head)
}
運行該程序：
$ go run main.go 1 <-> 2 <-> 3 <-> 4 <-> 5
擴展功能
可以為雙鏈表擴展其他功能，讀者可以思考如何實現(xiàn)
鏈表長度
func size(head *Node) int {
if head == nil {
fmt.Println("-> Empty list!")
return 0
}
count := 0
for head != nil {
count++
head = head.Next
}
return count
}
運行程序：
$ go run main.go 1 <-> 2 <-> 3 <-> 4 <-> 5 雙鏈表的長度: 5
插入
一個新節(jié)點可以很容易地插入到雙向鏈表中。我們只需要設(shè)置指針 prev_node 和 next_node 小心地將 prev_node 和 next_node 節(jié)點與適當?shù)闹羔樻溄悠饋怼?/p>
如果要在節(jié)點 n1 和 n3 之間插入節(jié)點 n2，則應(yīng)將 n2 的指針 prev_node 設(shè)置為 n1，將 n2 的指針 next_node 設(shè)置為 n3。
雙向鏈表中的插入可以通過多種方式完成：
- 在節(jié)點之間插入
- 在雙鏈表開頭插入
- 插入一個空鏈表
- 在雙鏈表末尾插入
刪除
在雙向鏈表中可以很容易地刪除節(jié)點。我們只需要將指針 prev_node 和 next_node 邏輯設(shè)置為節(jié)點。 可以通過以下方式刪除節(jié)點：
- 刪除最后的節(jié)點
- 刪除第一個節(jié)點
- 在節(jié)點之間刪除
反轉(zhuǎn)雙鏈表
假設(shè)我們有四個節(jié)點 n1、n2、n3 和 n4
反轉(zhuǎn)的步驟如下：
- 指針 head 指向最后一個節(jié)點 n4
- 由于 n4 現(xiàn)在是第一個節(jié)點，它的 prev_node 指針必須為 NULL
- 節(jié)點 n1 是最后一個節(jié)點，因此它的 next_node 必須為 NULL
- n4 的指針 next_node 指向 n3，n3 的 next_node 指向 n2，n2 的 next_node 指向 n1
- n1 的指針 prev_node 指向 n2，n2 的 prev_node 指向 n3，n3 的 prev_node 指向n4
總結(jié)
與單鏈表相比，雙鏈表具有多樣性，可以從任何方向遍歷雙向鏈表，從而更方便的插入和刪除元素。
但是為了維護每個節(jié)點的指針，會多一些額外的開銷。
參考鏈接：
以上就是Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學(xué)習教程的詳細內(nèi)容，更多關(guān)于Go 數(shù)據(jù)結(jié)構(gòu)雙鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解如何解決golang定時器引發(fā)的id重復(fù)問題
這篇文章主要為大家詳細介紹了如何解決golang定時器引發(fā)的id重復(fù)問題,文中的示例代碼講解詳細,感興趣的小伙伴可以跟隨小編一起學(xué)習一下2024-04-04
本文介紹了如何在Go語言項目中導(dǎo)入同級目錄和不同目錄的包,詳細解釋了創(chuàng)建文件結(jié)構(gòu)、編寫主函數(shù)、同級目錄和不同目錄方法的調(diào)用,適合初學(xué)者參考,幫助理解Go項目的基本構(gòu)建和包管理2024-09-09
go內(nèi)存緩存BigCache之Entry封裝源碼閱讀
這篇文章主要介紹了go內(nèi)存緩存BigCache之Entry封裝源碼閱讀2023-09-09
這篇文章主要介紹了Go語言設(shè)置JSON的默認值操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
Go語言集成開發(fā)環(huán)境之VS Code安裝使用
VS Code是微軟開源的一款編輯器，插件系統(tǒng)十分的豐富，下面介紹如何用VS Code搭建go語言開發(fā)環(huán)境,需要的朋友可以參考下2021-10-10
這篇文章主要介紹了圖文詳解go語言反射實現(xiàn)原理,本文圖文并茂給大家介紹的非常詳細，具有一定的參考借鑒價值，需要的朋友參考下吧，需要的朋友可以參考下2020-02-02
這篇文章主要給大家介紹了基于Go編寫一個可視化Navicat本地密碼解析器的方法,文中有詳細的代碼示例和圖文介紹,有需要的朋友可以參考閱讀本文2023-08-08
這篇文章主要介紹了GO語言映射（Map）用法,以實例形式較為詳細的分析了針對映射的創(chuàng)建、填充、遍歷及修改等操作的技巧,需要的朋友可以參考下2014-12-12
Go語言中的數(shù)據(jù)格式（json、xml?、msgpack、protobuf）使用總結(jié)
在分布式的系統(tǒng)中，因為涉及到數(shù)據(jù)的傳輸，所以一定會進行數(shù)據(jù)的交換，此時就要定義數(shù)據(jù)交換的格式，例如二進制、Json、Xml等等。本文總結(jié)了Go語言中的數(shù)據(jù)格式，對大家的學(xué)習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-07-07
這篇文章主要為大家介紹了Go語言入門Go?Web?Fiber框架的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05