日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

Go?語言數據結構之雙鏈表學習教程_Golang

作者：宇宙之一粟 ? 更新時間： 2022-10-26 編程語言

雙鏈表

雙鏈表 （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 &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

總結

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

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

參考鏈接：

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

原文鏈接：https://juejin.cn/post/7135829491124797453

欄目分類
最近更新