Go 語言資料結構之雙連結串列學習教學

2022-08-30 18:03:35

雙連結串列

雙連結串列（Doubly Linked List），每個節點持有一個指向列表前一個元素的指標，以及指向下一個元素的指標。

雙向連結串列的節點中包含 3 個欄位：

資料域 Value
一個 Next 指標指向雙連結串列中的下一個節點
一個 Prev 指標，指向雙連結串列中的前一個節點

結構體如下：

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 &amp;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()
}

為了測試，我們的完整程式碼：

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

擴充套件功能

可以為雙連結串列擴充套件其他功能，讀者可以思考如何實現

連結串列長度

func size(head *Node) int {
	if head == nil {
		fmt.Println("-&gt; 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

插入

一個新節點可以很容易地插入到雙向連結串列中。我們只需要設定指標 prev_node 和 next_node 小心地將 prev_node 和 next_node 節點與適當的指標連結起來。

如果要在節點 n1 和 n3 之間插入節點 n2，則應將 n2 的指標 prev_node 設定為 n1，將 n2 的指標 next_node 設定為 n3。

雙向連結串列中的插入可以通過多種方式完成：

在節點之間插入
在雙連結串列開頭插入
插入一個空連結串列
在雙連結串列末尾插入

刪除

在雙向連結串列中可以很容易地刪除節點。我們只需要將指標 prev_node 和 next_node 邏輯設定為節點。可以通過以下方式刪除節點：

刪除最後的節點
刪除第一個節點
在節點之間刪除

反轉雙連結串列

假設我們有四個節點 n1、n2、n3 和 n4

反轉的步驟如下：

指標 head 指向最後一個節點 n4
由於 n4 現在是第一個節點，它的 prev_node 指標必須為 NULL
節點 n1 是最後一個節點，因此它的 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

總結

與單連結串列相比，雙連結串列具有多樣性，可以從任何方向遍歷雙向連結串列，從而更方便的插入和刪除元素。

但是為了維護每個節點的指標，會多一些額外的開銷。

參考連結：

以上就是Go 語言資料結構之雙連結串列學習教學的詳細內容，更多關於Go 資料結構雙連結串列的資料請關注it145.com其它相關文章！