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!")开发者_JAVA return } for head != nil { if head.Next != nil { fmt.Printf("%d <-> ", head.Value) } else { fmt.Printf("%d ", head.Value) } head php= 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) n编程ode_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 nodjavascripte_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
总结
与单链表相比,双链表具有多样性,可以从任何方向遍历双向链表,从而更方便的插入和删除元素。
但是为了维护每个节点的指针,会多一些额外的开销。
参考链接:
- Doubly Linked List in Go (golang)
- Doubly Linked List (With code) (programiz.com)
以上就是Go 语言数据结构之双链表学习教程的详细内容,更多关于Go 数据结构双链表的资料请关注我们其它相关文章!
精彩评论