GO语言实现链表的增删改查

链表(Linked list)

链表是一种常见的数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存储到下一个节点的指针。由于不必须的顺序存储,链表在插入的时候可以到达O(1)的复杂度,比另一种线性表顺序快的多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序相应的时间复杂度分别是O(logn)和O(1)。

优点

链表通常由一连串的节点组成,每个节点包含任意的实例数据(data fields)和一或者两个用来指向上一个或者下一个的节点的位置的链接。链表最明显的好处是,常规的数字排列关联项目的方式可能不同于这些数据项目在记忆体或者磁盘上的顺序,数据的访问往往要在不同的排列书序中转换。二链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针。链表允许插入和移除表上任意位置的节点,但是不允许随机的存取。

分类

链表有很多种类型:单向链表双向链表循环链表

单向链表

它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。





双向链表

一种更复杂的链表是“双向链表”“双面链表”。每个节点有两个连接:一个指向前一个节点,(当此“连接”为第一个“连接”时,指向空值或者空列表);而另一个指向下一个节点,(当此“连接”为最后一个“连接”时,指向空值或者空列表)





循环链表

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。





代码实现

声明全局变量,保存头节点

  //头节点
var head *Node
//当前的节点,变化的
var curr *Node

声明节点类型

type Node struct{
//数据域
Data  string
//地址域,指向下一个节点
NextNode  *Node
}

创建头节点

func CreateHeadNode(data string)*Node{
//创建一个新节点
 var node *Node = new(Node)
 node.Data = data
 node.NextData = nil
 //保存头节点
 head = node
 //将curr指向头节点
 curr = node
 return node
 
}

添加新节点

func AddNode(data string)*Node{
//创建新节点
var newNode *node = new(Node)
// 新节点赋值
newNode.Data = data
newNode.NextNode = nil
//将当前节点,也就是创建的头节点 或者要添加的上一个节点的NextNode指向新节点newNode
curr.NextNode = newNode
// 将新节点赋值给curr节点
curr = newNode
 return newNode

}

遍历链表

func ShowNodes{
//将头节点赋值给node节点
var node = head

for {
 
 //如果头节点的地址域为空,那么这个链表只有头,直接打印
 if node.NextNode == nil{
  fmt.Print(node.Data)
  break
 }else{
 //将下一个节点赋值给node
 fmt.Println(node.Data)
 node = node.NextNode
 } 
}
}

计算节点的个数

func NodeCnt() int {
	var cnt int = 1
	var node = head
	for {
		if node.NextNode == nil {
			break
		} else {
			node = node.NextNode
			cnt = cnt + 1
		}

	}
	return cnt
}

插入节点

func InsertNodeByIndex(index int,data string) *Node{
//在第一个位置插入
if index == 0{
 var node *Node = new(Node)
 node.Data = data
// 将新节点的地址域指向原来的头节点
 node.NextNode = head
 将新节点设为头节点
 head = node
}else if (index > NodeCnt()- 1){ // 在尾部插入
 AddNode(data)
}else{

var n = head
//遍历找到要插入节点的位置的节点
for (i:= 0;i< index -1;i++)
{
  n = n.NextNode
}

var newNode *Node = new(Node)
newNode.Data  = data
//将新节点的地址域指向下找到节点的下一个节点
newNode.NextNode = n.NextNode
//将找到节点的地址域指向新节点
n.NextNode = newNode
}
return nil

}

删除节点

func DeleteNodeByIndex(index int){
 
 var node = head
 if index == 0{
 //删除头节点,就是第二个节点为头节点
 head = node.NextNode
 }else{
 //找到要删除的节点的前一个节点
 for(i:=0;i< index-1;i++){
   node = node.NextNode
 }

 node.NextNode = node.NextNode.NextNode

 } 
}

Go语言中是自动垃圾回收机制,断开链接的那个节点,在程序运行结束时自动销毁

修改指定节点内容

func UpdateNodeByIndex(index int,data string){

var node = head
if index == 0{
  head.Data = data
}else{
 for i := 0; i < index; i++ {
			node = node.NextNode
		}
		node.Data = data
}
 
}

总结

本文只是实现了简单的单向链表的基本操作,下一章将讲述一下链表的实际应用之一,Map的实现原理即行Hash散列原理


github源代码

喜欢就star一下吧!👻👻👻

作者原创,转载请注明出处,如有错误描述,请评论纠正,谢谢大家!🐳🐳🐳

打赏一个呗

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦