开发者

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

目录
  • 双链表
  • 创建节点
  • 双链表遍历
  • 扩展功能
    • 链表长度
    • 插入
    • 删除
    • 反转双链表
  • 总结

    双链表

    双链表 (Doubly Linked List),每个节点持有一个指向列表前一个元素的指针,以及指向下一个元素的指针。

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

    双向链表的节点中包含 3 个字段:

    • 数据域 Value
    • 一个 Next 指针指向双链表中的下一个节点
    • 一个 Prev 指针,指向双链表中的前一个节点

    结构体如下:

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

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

    实际应用: 音乐播放器的播放列表,使用双向链表可以快速访问上一个歌曲和下一首歌曲。

    创建节点

    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
    	nphpode_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 
    

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

    扩展功能

    可以为双链表扩展其他功能,读者可以思考如何实现

    链表长度

    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)

    以上就是Go 语言数据结构之双链表学习教程的详细内容,更多关于Go 数据结构双链表的资料请关注我们其它相关文章!

    0

    上一篇:

    下一篇:

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    最新开发

    开发排行榜