雙鏈表

雙鏈表 （Doubly Linked List），每個(gè)節(jié)點(diǎn)持有一個(gè)指向列表前一個(gè)元素的指針，以及指向下一個(gè)元素的指針。

雙向鏈表的節(jié)點(diǎn)中包含 3 個(gè)字段：

• 數(shù)據(jù)域 Value
• 一個(gè) Next 指針指向雙鏈表中的下一個(gè)節(jié)點(diǎn)
• 一個(gè) Prev 指針，指向雙鏈表中的前一個(gè)節(jié)點(diǎn)

結(jié)構(gòu)體如下：

type Node struct {
	Prev  *Node
	Value int
	Next  *Node
}

實(shí)際應(yīng)用： 音樂播放器的播放列表，使用雙向鏈表可以快速訪問上一個(gè)歌曲和下一首歌曲。

創(chuàng)建節(jié)點(diǎn)

func CreateNewNode(value int) *Node {
	var node Node
	node.Next = nil
	node.Value = value
	node.Prev = nil
	return &node
}

雙鏈表遍歷

雙向鏈表的遍歷與單鏈表的遍歷類似。我們必須首先檢查一個(gè)條件：鏈表是否為空。這有助于將開始指針設(shè)置在適當(dāng)?shù)奈恢谩Ｖ笪覀冊(cè)L問每個(gè)節(jié)點(diǎn)直到結(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()
}

為了測(cè)試，我們的完整代碼：

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)
}

運(yùn)行該程序：

$ go run main.go
1 <-> 2 <-> 3 <-> 4 <-> 5 

擴(kuò)展功能

可以為雙鏈表擴(kuò)展其他功能，讀者可以思考如何實(shí)現(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
}

運(yùn)行程序：

$ go run main.go
1 <-> 2 <-> 3 <-> 4 <-> 5 
雙鏈表的長度:  5

插入

一個(gè)新節(jié)點(diǎn)可以很容易地插入到雙向鏈表中。我們只需要設(shè)置指針 prev_node 和 next_node 小心地將 prev_node 和 next_node 節(jié)點(diǎn)與適當(dāng)?shù)闹羔樻溄悠饋怼?/p>

如果要在節(jié)點(diǎn) n1 和 n3 之間插入節(jié)點(diǎn) n2，則應(yīng)將 n2 的指針 prev_node 設(shè)置為 n1，將 n2 的指針 next_node 設(shè)置為 n3。

雙向鏈表中的插入可以通過多種方式完成：

• 在節(jié)點(diǎn)之間插入
• 在雙鏈表開頭插入
• 插入一個(gè)空鏈表
• 在雙鏈表末尾插入

刪除

在雙向鏈表中可以很容易地刪除節(jié)點(diǎn)。我們只需要將指針 prev_node 和 next_node 邏輯設(shè)置為節(jié)點(diǎn)。 可以通過以下方式刪除節(jié)點(diǎn)：

• 刪除最后的節(jié)點(diǎn)
• 刪除第一個(gè)節(jié)點(diǎn)
• 在節(jié)點(diǎn)之間刪除

反轉(zhuǎn)雙鏈表

假設(shè)我們有四個(gè)節(jié)點(diǎn) n1、n2、n3 和 n4

反轉(zhuǎn)的步驟如下：

• 指針 head 指向最后一個(gè)節(jié)點(diǎn) n4
• 由于 n4 現(xiàn)在是第一個(gè)節(jié)點(diǎn)，它的 prev_node 指針必須為 NULL
• 節(jié)點(diǎn) n1 是最后一個(gè)節(jié)點(diǎn)，因此它的 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é)

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

但是為了維護(hù)每個(gè)節(jié)點(diǎn)的指針，會(huì)多一些額外的開銷。

參考鏈接：

• Doubly Linked List in Go (Golang)
• Doubly Linked List (With code) (programiz.com)

以上就是Go 語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表學(xué)習(xí)教程的詳細(xì)內(nèi)容，更多關(guān)于Go 數(shù)據(jù)結(jié)構(gòu)雙鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論