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("-&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

总结

与单链表相比，双链表具有多样性，可以从任何方向遍历双向链表，从而更方便的插入和删除元素。

但是为了维护每个节点的指针，会多一些额外的开销。

参考链接：

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

赞 (0)

相关推荐

  • Go语言数据结构之选择排序示例详解

    Go语言数据结构之选择排序示例详解

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • Go语言数据结构之插入排序示例详解

    Go语言数据结构之插入排序示例详解

    目录 插入排序 动画演示 Go 代码实现 总结 插入排序 插入排序,英文名(insertion sort)是一种简单且有效的比较排序算法. 思想: 在每次迭代过程中算法随机地从输入序列中移除一个元素,并将改元素插入待排序序列的正确位置.重复该过程,直到所有输入元素都被选择一次,排序结束. 插入排序有点像小时候我们抓扑克牌的方式,如果抓起一张牌,我们放在手里:抓起第二张的时候,会跟手里的第一张牌进行比较,比手里的第一张牌小放在左边,否则,放在右边. 因此,对所有的牌重复这样的操作,所以每一次都是插

  • Go语言数据结构之希尔排序示例详解

    Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • Go 数据结构之堆排序示例详解

    Go 数据结构之堆排序示例详解

    目录 堆排序 堆排序过程 动画显示 开始堆排序 代码实现 总结 堆排序 堆排序是一种树形选择排序算法. 简单选择排序算法每次选择一个关键字最小的记录需要 O(n) 的时间,而堆排序选择一个关键字最小的记录需要 O(nlogn)的时间. 堆可以看作一棵完全二叉树的顺序存储结构. 在这棵完全二叉树中,如果每个节点的值都大于等于左边孩子的值,称为大根堆(最大堆.又叫大顶堆).如果每个节点的值都小于等于左边孩子的值,称为小根堆(最小堆,小顶堆). 可以,用数学符号表示如下: 堆排序过程 构建初始堆 在输

  • go数据结构和算法BitMap原理及实现示例

    目录 1. BitMap介绍 如何判断数字在bit数组的位置 设置数据到bit数组 从bit数组中清除数据 数字是否在bit数组中 2. Go语言位运算 左移 右移 使用&^和位移运算来给某一位置0 3. BitMap的Go语言实现 定义 创建BitMap结构 将数据添加到BitMap 从BitMap中删除数据 判断BitMap中是否存在指定的数据 1. BitMap介绍 BitMap可以理解为通过一个bit数组来存储特定数据的一种数据结构.BitMap常用于对大量整形数据做去重和查询.在这类查

  • Go反射底层原理及数据结构解析

    Go反射底层原理及数据结构解析

    目录 1. 反射的引入与介绍 2. 反射的数据结构 3. 如何通过反射对象来修改原数据对象的值? 1. 反射的引入与介绍 在计算机科学中,反射是指计算机程序在运行时(Run time)可以访问.检测和修改它本身状态或行为的一种能力.用比喻来说,反射就是程序在运行的时候能够“观察”并且修改自己的行为. 需要反射的 2 个常见场景: 有时你需要编写一个函数,但是并不知道传给你的参数类型是什么,可能是没约定好:也可能是传入的类型很多,这些类型并不能统一表示.这时反射就会用的上了. 有时候需要根据某些条

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

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

    目录 双链表 创建节点 双链表遍历 扩展功能 链表长度 插入 删除 反转双链表 总结 双链表 双链表 (Doubly Linked List),每个节点持有一个指向列表前一个元素的指针,以及指向下一个元素的指针. 双向链表的节点中包含 3 个字段: 数据域 Value 一个 Next 指针指向双链表中的下一个节点 一个 Prev 指针,指向双链表中的前一个节点 结构体如下: type Node struct { Prev *Node Value int Next *Node } 实际应用: 音乐

  • C语言数据结构之单链表与双链表的增删改查操作实现

    C语言数据结构之单链表与双链表的增删改查操作实现

    目录 前言 单链表的增删改查 定义结构体以及初始化 增加结点 删除结点 查找修改结点 移除结点 最终效果 双链表的基本操作 初始化建表 遍历双链表 指定位置插入结点 指定位置删除结点 查找结点位置 最终效果 结语 前言 上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求 构造带有头结点的

  • C语言实现循环双链表

    C语言实现循环双链表

    本文实例为大家分享了C语言实现循环双链表的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int DataType; typedef struct Node { DataType data; // 数据域 struct Node * prior; // 前趋指针 struct Node * next; // 后继指针 }LinkList; LinkLis

  • C语言数据结构之单链表的实现

    C语言数据结构之单链表的实现

    目录 一.为什么使用链表 二.链表的概念 三.链表的实现 3.1 创建链表前须知 3.2 定义结构体 3.3 申请一个节点 3.4 链表的头插 3.5 链表的尾插 3.6 链表的尾删 3.7 链表的头删 3.8 寻找某节点 3.9 在指定节点前插入节点 3.10 删除指定节点前的节点 3.11 链表的销毁 一.为什么使用链表 在学习链表以前,我们存储数据用的方式就是数组.使用数组的好处就是便于查找数据,但缺点也很明显. 使用前需声明数组的长度,一旦声明长度就不能更改 插入和删除操作需要移动大量的

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • C语言数据结构之使用链表模拟栈的实例

    C语言数据结构之使用链表模拟栈的实例

    C语言数据结构之使用链表模拟栈的实例 以下是"使用链表模拟栈"的简单示例: 1. 用C语言实现的版本 #include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct node{ datatype data; struct node *next; } stack; stack* m_stack = NULL; /* 创建链表,从表头插入新元素 */ void creat(void

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • C语言数据结构之复杂链表的拷贝

    C语言数据结构之复杂链表的拷贝

    题目: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点. 构造这个链表的 深拷贝. 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值.新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态.复制链表中的指针都不应指向原链表中的节点 . 例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y

  • C语言数据结构之单链表存储详解

    C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

  • C语言数据结构之单链表操作详解

    C语言数据结构之单链表操作详解

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

随机推荐