目录双链表创建节点双链表遍历扩展功能链表长度插入删除反转双链表总结双链表 双链表 (Doubly Linked List),每个节点持有一个指向列表前一个元素的指针,以及指向下一个元
双链表 (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
反转的步骤如下:
与单链表相比,双链表具有多样性,可以从任何方向遍历双向链表,从而更方便的插入和删除元素。
但是为了维护每个节点的指针,会多一些额外的开销。
参考链接:
--结束END--
本文标题: Go语言数据结构之双链表学习教程
本文链接: https://www.lsjlt.com/news/121112.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
2024-04-05
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0