详解go语言单链表及其常用方法的实现
作者:Zppj 发布时间:2024-02-21 03:13:41
目的
在刷算法题中经常遇到关于链表的操作,在使用go语言去操作链表时不熟悉其实现原理,目的是为了重温链表这一基础且关键的数据结构。
1、链表的特点和初始化
1.1、链表的特点
用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)
1.2、结点
结点(node)
数据域 => 存储元素信息
指针域 => 存储结点的直接后继,也称作指针或链
首元结点 是指链表中存储的第一个数据元素的结点
头结点 是在首元结点之前附设的一个结点,其指针域指向首元结点(非必须)
头指针 是指向链表中第一个结点的指针
1.3、单链表
特点
每个结点中只包含一个指针域
单链表是非随机存取的存储结构,要取得第i个数据元素必须从头指针出发,顺链进行寻找,也称为顺序存取的存取结构
1.4、单链表的常用操作
本文主要实现了单链表的以下操作
判断是否为空
获取链表长度
在头部插入元素
在尾部插入元素
删除指定位置元素
删除指定值的元素
查找是否包含指定值
查找指定位置元素的值
遍历链表所有结点
1.5、单链表的初始化
//定义单链表结构体
type Node struct {
data interface{} //数据域
next *Node //指针域
}
type List struct {
length int //储存链表的长度
headNode *Node
}
/*单链表的初始化
1、生成新结点作为头结点,用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
//即构造一个空的单链表L(包含头指针)
node := new(Node)
L := new(List)
L.headNode = node
return L
}
2、单链表的插入
先讲单链表的插入有利于后续相关操作的实现
2.1、在指定位置插入元素
/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上,即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
if index <= 0 || index > list.length {
fmt.Println("err")
} else {
pre := list.headNode
node := &Node{data: v}
if index == 1 {
node.next = pre
list.headNode = node
} else {
for count := 1; count < index-1; count++ {
pre = pre.next
}
node.next = pre.next
pre.next = node
}
list.length--
}
}
2.2、在头部插入元素
func (list *List) AddElem(v interface{}) {
node := &Node{data: v}
if list.IsNull() { //处理空表的插入,否则会导致一个空的头结点后移
list.headNode = node
list.length++
return
}
node.next = list.headNode
list.headNode = node
list.length++
return
}
2.3、在尾部插入元素
func (list *List) AppendElem(v interface{}) {
node := &Node{data: v}
if list.IsNull() {
list.headNode.next = node
} else {
cur := list.headNode
for cur.next != nil {
cur = cur.next
}
cur.next = node
}
list.length++
return
}
3、单链表的删除
3.1、删除指定值的元素
/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中,以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
if index <= 0 || index > list.length {
fmt.Println("删除位置不合理")
return
} else {
pre := list.headNode
if index == 1 {
list.headNode = pre.next
} else {
pre := list.headNode
for count := 1; count < index-1; count++ {
pre = pre.next
}
pre.next = pre.next.next
}
list.length--
}
}
3.2、删除指定位置的元素
func (list *List) RemoveElem(v interface{}) {
pre := list.headNode
if pre.data == v {
list.headNode = pre.next
fmt.Println("ok")
} else {
for pre.next != nil {
if pre.next.data == v {
pre.next = pre.next.next
fmt.Println("ok")
return
} else {
pre = pre.next
}
}
fmt.Println("fail")
return
}
}
4、单链表的查询
4.1、查找是否包含指定值
/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找,只要指向当前结点的指针p不为空,
并且p所指结点的数据域不等于给定值e,则执行以下操作:p指向下一个结点
3、返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
if IsNull() {
fmt.Println("err")
} else {
pre := list.headNode
for pre != nil {
if pre.data == v {
return true
}
pre = pre.next
}
return false
}
}
4.2、查找指定位置的值
/*单链表的取值
1、用指针P指向首元结点,用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问,
只要指向当前结点的指针P不为空,并且没有达到序号为i的结点,则循环执行以下操作:
2.1、P指向下一个结点
2.2、计数器j相应加1
3、退出循环时,如果指针P为空,或者计数器j大于i,说明指定的序号i值不合法(i大于表长n或i小于等于0),
取值失败返回ERROR;否则取值成功,
此时j==i时,P所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK
*/
func (list *List) GetElem(index int) int {
if index <= 0 || index > list.length {
fmt.Println("err")
return
} else {
pre := list.headNode
for j := 0; j < index; j++ {
if pre != nil {
pre = pre.next
}
}
return pre.data
}
}
4.3、遍历单链表
func (list *List) ShowList() {
if !list.IsNull() {
cur := list.headNode
for {
fmt.Printf("\t%v", cur.data)
if cur.next != nil {
cur = cur.next
} else {
break
}
}
}
}
5、完整代码及结果展示
package main
import "fmt"
//定义单链表结构体
type Node struct {
data interface{} //数据域
next *Node //指针域
}
type List struct {
length int //储存链表的长度
headNode *Node
}
/*
type Method interface {
IsNull() bool //1、判断是否为空
GetLength() int //2、获取链表长度
InsertElem(i int, v interface{}) //3、在指定位置添加元素
AddElem(v interface{}) //4、在头部插入元素
AppendElem(v interface{}) //5、在尾部插入元素
DeleteElem(i int) //6、删除指定位置元素
RemoveElem(v interface{}) //7、删除指定值的元素
ContaineElem(v interface{}) bool //8、是否包含指定值的元素
LocateElem(i int) interface{} //9、查找指定位置元素的值
ShowList() //10、遍历链表所有结点
}
*/
/*单链表的初始化
1、生成新结点作为头结点,用头指针指向头结点
2、头结点的指针域置空
*/
func InitList() *List {
//即构造一个空的单链表L(包含头指针)
node := new(Node)
L := new(List)
L.headNode = node
return L
}
/*单链表的取值
1、用指针P指向首元结点,用j做计数器初值赋为1
2、从首元结点开始依次顺着链域(指针域)next向下访问,只要指向当前结点的指针P不为空,
并且没有达到序号为i的结点,则循环执行以下操作:
2.1、P指向下一个结点
2.2、计数器j相应加1
3、退出循环时,如果指针P为空,或者计数器j大于i,说明指定的序号i值
不合法(i大于表长n或i小于等于0),取值失败返回ERROR;否则取值成功,
此时j==i时,P所指的结点就是要找的第i个结点,用参数e保存当前结点的数据域,返回OK
*/
func (list *List) GetElem(index int) int {
if index <= 0 || index > list.length {
return 0
} else {
pre := list.headNode
for j := 0; j < index-1; j++ {
if pre != nil {
pre = pre.next
}
}
return pre.data.(int)
}
}
/*单链表的按值查找
1、用指针p指向首元结点
2、从首元结点开始以此顺着链域next向下查找,只要指向当前结点的
指针p不为空,并且p所指结点的数据域不等于给定值e,则执行以下操作:
2.1、p指向下一个结点
3、返回p。若查找成功,p此时即为结点的地址值,若查找失败,p的值即为NULL。
*/
func (list *List) LocateElem(v interface{}) bool {
if list.IsNull() {
fmt.Println("err")
return false
} else {
pre := list.headNode
for pre != nil {
if pre.data == v {
return true
}
pre = pre.next
}
return false
}
}
/*单链表的插入=>将值为e的新结点插入到表的第i个结点的位置上,即插入到结点a(i-1)与a(i)之间
1、查找结点a(i-1)并由指针p指向该结点
2、生成一个新结点*s
3、将新结点*s的数据域置为e
4、将新结点*s的指针域指向结点a(i)
5、将结点*p的指针域指向新结点*s
*/
func (list *List) InsertElem(index int, v interface{}) {
if index <= 0 || index > list.length {
fmt.Println("err")
} else {
pre := list.headNode
node := &Node{data: v}
if index == 1 {
node.next = pre
list.headNode = node
} else {
for count := 1; count < index-1; count++ {
pre = pre.next
}
node.next = pre.next
pre.next = node
}
list.length--
}
}
/*单链表的删除
1、查找结点a(i-1)并由指针p指向该结点
2、临时保存待删除结点a(i)的地址在q中,以备释放
3、将结点*p的指针域指向a(i)的直接后继结点
4、释放结点a(i)的空间
*/
func (list *List) DeleteElem(index int) {
if index <= 0 || index > list.length {
fmt.Println("删除位置不合理")
return
} else {
pre := list.headNode
if index == 1 {
list.headNode = pre.next
} else {
pre := list.headNode
for count := 1; count < index-1; count++ {
pre = pre.next
}
pre.next = pre.next.next
}
list.length--
}
}
func (list *List) RemoveElem(v interface{}) {
pre := list.headNode
if pre.data == v {
list.headNode = pre.next
} else {
for pre.next != nil {
if pre.next.data == v {
pre.next = pre.next.next
return
} else {
pre = pre.next
}
}
fmt.Println("fail")
return
}
}
func (list *List) IsNull() bool {
if list.length == 0 {
return true
} else {
return false
}
}
func (list *List) AddElem(v interface{}) {
node := &Node{data: v}
if list.IsNull() { //处理空表的插入,否则会导致一个空的头结点后移
list.headNode = node
list.length++
return
}
node.next = list.headNode
list.headNode = node
list.length++
return
}
func (list *List) AppendElem(v interface{}) {
node := &Node{data: v}
if list.IsNull() {
list.headNode.next = node
} else {
cur := list.headNode
for cur.next != nil {
cur = cur.next
}
cur.next = node
}
list.length++
return
}
func (list *List) ShowList() {
if !list.IsNull() {
cur := list.headNode
for {
fmt.Printf("\t%v", cur.data)
if cur.next != nil {
cur = cur.next
} else {
break
}
}
fmt.Printf("\n")
}
}
func main() {
L := InitList()
msg := []int{12, 5, 3, 8, 55, 13}
for i := range msg {
L.AddElem(msg[i])
}
fmt.Println("---- 添加元素 ----")
L.AppendElem(66)
L.ShowList()
fmt.Println("---- 按位删除元素 ----")
L.DeleteElem(3)
L.ShowList()
fmt.Println("---- 按值删除元素 ----")
L.RemoveElem(13)
L.ShowList()
fmt.Println("---- 插入元素 ----")
L.InsertElem(1, 88)
L.ShowList()
fmt.Println("---- 按值寻找元素 ----")
fmt.Println(L.LocateElem(88))
fmt.Println("---- 按位寻找元素 ----")
fmt.Println(L.GetElem(4))
}
结果
---- 添加元素 ----
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语言实现单链表
来源:https://studygolang.com/articles/31855
![](https://www.aspxhome.com/images/zang.png)
![](https://www.aspxhome.com/images/jiucuo.png)
猜你喜欢
- 身边的人竟然不玩“跳一跳了”,都迷上了一个叫“冲顶大会”的东西,考了很多各学科的冷知识,文学、数学、地理、生物、动漫、八卦…小编网上找到一些
- channel单纯地将函数并发执行是没有意义的。函数与函数间需要交换数据才能体现并发执行函数的意义。虽然可以使用共享内存进行数据交换,但是共
- 本文实例讲述了python读写配置文件操作。分享给大家供大家参考,具体如下:在用编译型语言写程序的时候,很多时候用到配置文件,作为一个约定的
- 如果使用Python做大型海量数据批量任务时,并且backend用mongodb做数据储存时,常常面临大量读写数据库的情况。尤其是大量更新任
- 可以写一个函数: 主要是使用正则来判断。另外输入字符是空的话,使用"-"来替换。CREATE FUNCTION [dbo
- 对于opencv 它提供了许多已经练习好的模型可供使用,我们需要通过他们来进行人脸识别参考了网上许多资料 假设你已经配好了开发环境
- 本文实例为大家分享了Python实现简单飞机大战的具体代码,供大家参考,具体内容如下功能玩家飞机可以移动,可以发射 * ,敌机随机产生,自由坠
- 本文实例讲述了Sanic框架应用部署方法。分享给大家供大家参考,具体如下:简介Sanic是一个类似Flask的Python 3.5+ Web
- 有时,我们需要获得某张表所有的元数据,我们可能想到的是通过查询系统表获得,但是这比较繁琐,而在SQL Server2005(包含)以后,提供
- 本文实例为大家分享了python tkinter实现学生信息管理系统的具体代码,供大家参考,具体内容如下初学python,代码写的比较繁杂,
- 前言大部分人在日常的业务开发中,其实很少去关注数据库的事务相关问题,基本上都是 CURD 一把梭。正好最近在看 MySQL 的相关基础知识,
- 关于python3中的追加写入excel问题,这个问题坑了我几小时,其实加一个参数即可。因为之前有写好的excel,想追加写入,但是写入后却
- 一、 安装tensorboard直接pip即可:pip install tensorboard这里注意,使用pytorch,并不需要额外安装
- CLI工程全局安装vue-clinpm install -g @vue/cli通过cli创建uni-app项目 vue creat
- 本文实例为大家分享了H5+css3+js搭建带验证码的登录页面,供大家参考,具体内容如下login.html<!DOCTYPE HTM
- 首先,看一下sql server,之前我们都通过前台用户选择一个起始时间和一个结束时间(以日为最小单位),然后来作为条件进行查询,如果直接通
- 前言众所周知,python拥有丰富的内置库,还支持众多的第三方库,被称为胶水语言,随机函数库random,就是python自带的标准库,他的
- 先来看看架构,如下图:部署1.修改hosts在所有的服务器中执行相同的操作。vim /etc/hosts192.168.137.10 mas
- 最近vue更新的2.0版本,唉,我是在2.0版本前学习的,现在更新了又要看一遍了,关键是我之前看了3个星期2.0就更新了,vux还没同步更新
- 在Python面向对象编程中的类构建中,有时候会遇到@classmethod的用法。总感觉有这种特殊性说明的用法都是高级用法,在我这个层级的