Go语言之单链表实现插入元素

单链表简介

单链表是一种顺序存储的结构。 有一个头结点，没有值域，只有连域，专门存放第一个结点的地址。 有一个尾结点，有值域，也有链域，链域值始终为NULL。 所以，在单链表中为找第i个结点或数据元素，必须先找到第i - 1 结点或数据元素，而且必须知道头结点，否则整个链表无法访问。

示例：

定义结构体

package main import "fmt" type Object interface{} type Node struct { Data Object //定义数据域 Next *Node //定义地址域(指向下一个表的地址) } type List struct { headNode *Node //头节点 }

判断链表是否为空

//创建IsEmpty方法，返回bool类型 func (this *List）ISEmpty() bool { //判断单链表是否为空，只需要判断头节点是否为空即可 if this.headNode == nil { return true }else { return false } }

获取链表长度

func (this *List) Length() int { //获取链表头结点 first := this.headNode //定义一个计数器，初始值为0 count := 0 for first != nil { //如果头节点不为空，则count++ count ++ //对地址进行逐个位移 first = first.Next } return count }

从链表头部添加元素

func (this *List) Add(data Object) *Node { node := &Node{Data: data} node.Next = this.headNode this.headNode = node return node }

从链表尾部添加元素

func (this *List）Append(data object） { //创建一个新元素，通过传入data参数进行数据域的赋值 node := &Node{Data: data} if this.IsEmpty(){ //如果该链表为空，那么直接将新元素作为头节点 this.headNode=node }else { //如果链表不为空 cur := this.headNode//定义变量用于存储头节点 for cur.Next != nil {//判断是否为尾结点，如果=nil,则该节点是尾节点 cur = cur.Next /链表进行位移，知道cur获取到尾节点 } cur.Next = node//此时cur为尾节点，将其地址域指向新创建的节点 } }

链表指定位置添加元素

//在指定位置添加元素，此处的index指下标，this.headNode的index=0 func (this *List）Insert(index int,data Object）{ if index < o{ //如果index<0，则进行头部插入 this .Add(data) }else if index > this.Length(){ //如果index >链表长度，则进行尾部插入 this.Append(data) }else { pre := this.headNode count := 0 for count< (index -1){//用于控制位移的链表数目 pre = pre.Next count++ } //当循环退出后，pre指向index-1的位置 node:= &Node{Data: data} //创建新的链表元素 node.Next = pre.Next //将新的链表元素地址指向其上一个链表地址域存储的地址(也就是新元素现在的跟随元素) pre.Next = node //上一个链表地址域存储的地址指向新元素地址 }

删除链表指定值的元素

//删除指定元素 func (this *List) Remove(data Object){ pre := this.headNode //定义变量pre，存储头结点 if pre.Data == data{ //如果该节点的数据域的值为data this.headNode = pre.Next //如果就是删除头结点，那么第二个节点就是新的头节点 }else { //如果删除的不是头节点 for pre.Next !=nil { //循环判断是否遍历到最后一个节点，如果不是，则进行如下判断 if pre.Next.Data == data { //如果pre.Next的节点的数据等于data，那么删除该节点，pre.Next指向该节点之后的节点地址 pre.Next = pre.Next.Next } else { //如果pre.Next的节点的数据等于data，那么进行节点位移，循环判断 pre = pre.Next } } } }