详解go语言单链表及其常用方法的实现
目的
在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构。
1、链表的特点和初始化
1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)
1.2、结点
结点(node)
- 数据域 => 存储元素信息
- 指针域 => 存储结点的直接后继,也称作指针或链
首元结点 是指链表中存储的第一个数据元素的结点
头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须)
头指针 是指向链表中第一个结点的指针
1.3、单链表
特点
- 每个结点中只包含一个指针域
- 单链表是非随机存取的存储结构,要取得第i个数据元素必须从头指针出发,顺链进行寻找,也称为顺序存取的存取结构
1.4、单链表的常用操作
本文主要实现了单链表的以下操作
- 判断是否为空
- 获取链表长度
- 在头部插入元素
- 在尾部插入元素
- 删除指定位置元素
- 删除指定值的元素
- 查找是否包含指定值
- 查找指定位置元素的值
- 遍历链表所有结点
1.5、单链表的初始化
2、单链表的插入
先讲单链表的插入有利于后续相关操作的实现
2.1、在指定位置插入元素
2.2、在头部插入元素
2.3、在尾部插入元素
3、单链表的删除
3.1、删除指定值的元素
3.2、删除指定位置的元素
4、单链表的查询
4.1、查找是否包含指定值
4.2、查找指定位置的值
4.3、遍历单链表
5、完整代码及结果展示
结果
---- 添加元素 ----
13 55 8 3 5 12 66
---- 按位删除元素 ----
13 55 3 5 12 66
---- 按值删除元素 ----
55 3 5 12 66
---- 插入元素 ----
88 55 3 5 12 66
---- 按值寻找元素 ----
true
---- 按位寻找元素 ----
5
6、总结
本文中除了初始化时为链表添加了一个空的头结点,其他情况下均无头结点,正如书中所说,为单链表添加头结点会方便很多,对链表进行相关操作时,不需要对首元结点做额外的处理,也便于对空表和非空表做统一处理
关于删除时释放结点空间及指针回收,我们交由go强大的垃圾回收来完成
参考博客
golang之单链表实现
到此这篇关于详解go语言单链表及其常用方法的实现的文章就介绍到这了,更多相关go语言单链表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!
上一篇: Vue实现图书管理小案例
下一篇: 连小朋友都笑尿了