登录
首页 >  Golang >  Go教程

Go语言数据结构之双链表学习教程

来源:脚本之家

时间:2022-12-30 18:27:00 280浏览 收藏

亲爱的编程学习爱好者,如果你点开了这篇文章,说明你对《Go语言数据结构之双链表学习教程》很感兴趣。本篇文章就来给大家详细解析一下,主要介绍一下数据结构、双链表,希望所有认真读完的童鞋们,都有实质性的提高。

双链表

双链表 (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("-> 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语言数据结构之双链表学习教程》的介绍应该让你收获多多了吧!欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布Golang相关知识,快来关注吧!

声明:本文转载于:脚本之家 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表