单向链表

单向链表(单链表)是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表，因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;

特点：

(1)单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小

(2)结点的删除非常方便，不需要像线性结构那样移动剩下的数据

(3)结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表

packagemainimport("fmt")typeLinkNodestruct{Datainterface{}Next*LinkNode}typeSingleLinkstruct{head*LinkNodetail*LinkNodesizeint}//初始化链表funcInitSingleLink()(*SingleLink){return&SingleLink{head:nil,tail:nil,size:0,}}//获取头部节点func(sl*SingleLink)GetHead()*LinkNode{returnsl.head}//获取尾部节点func(sl*SingleLink)GetTail()*LinkNode{returnsl.tail}//打印链表func(sl*SingleLink)Print(){fmt.Println("SingleLinksize:",sl.Length())ifsl.size==0{return}ptr:=sl.GetHead()forptr!=nil{fmt.Println("Data:",ptr.Data)ptr=ptr.Next}}//链表长度func(sl*SingleLink)Length()int{returnsl.size}//插入数据（头插）func(sl*SingleLink)InsertByHead(node*LinkNode){ifnode==nil{return}//判断是否第一个节点ifsl.Length()==0{sl.head=nodesl.tail=nodenode.Next=nil}else{oldHeadNode:=sl.GetHead()sl.head=nodesl.head.Next=oldHeadNode}sl.size++}//插入数据（尾插）func(sl*SingleLink)InsertByTail(node*LinkNode){ifnode==nil{return}//插入第一个节点ifsl.size==0{sl.head=nodesl.tail=nodenode.Next=nil}else{sl.tail.Next=nodenode.Next=nilsl.tail=node}sl.size++}//插入数据（下标）位置func(sl*SingleLink)InsertByIndex(indexint,node*LinkNode){ifnode==nil{return}//往头部插入ifindex==0{sl.InsertByHead(node)}else{ifindex>sl.Length(){return}elseifindex==sl.Length(){//往尾部添加节点sl.InsertByTail(node)}else{preNode:=sl.Search(index-1)//下标为index的上一个节点currentNode:=sl.Search(index)//下标为index的节点preNode.Next=nodenode.Next=currentNodesl.size++}}}//删除数据（下标）位置func(sl*SingleLink)DeleteByIndex(indexint){ifsl.Length()==0||index>sl.Length(){return}//删除第一个节点ifindex==0{sl.head=sl.head.Next}else{preNode:=sl.Search(index-1)ifindex!=sl.Length()-1{nextNode:=sl.Search(index).NextpreNode.Next=nextNode}else{sl.tail=preNodepreNode.Next=nil}}sl.size--}//删除数据（数据）func(sl*SingleLink)DeleteByData(Datainterface{}){ifsl.Length()==0||Data==nil{return}node:=sl.headpreNode:=sl.headfornode.Next!=nil{preNode=nodenode=node.Nextifnode.Data.(int)==Data.(int){preNode.Next=node.Nextnode.Next=nilnode.Data=nilnode=nilreturn}}}//查询数据func(sl*SingleLink)Search(indexint)(node*LinkNode){ifsl.Length()==0||index>sl.Length(){returnnil}//是否头部节点ifindex==0{returnsl.GetHead()}node=sl.headfori:=0;i<=index;i++{node=node.Next}return}//销毁链表func(sl*SingleLink)Destroy(){sl.tail=nilsl.head=nilsl.size=0}funcmain(){//初始化链表sl:=InitSingleLink()//指定指标插入fori:=0;i<5;i++{snode:=&LinkNode{Data:i,}sl.InsertByIndex(i,snode)}sl.Print()fmt.Println("===============================")varsnode*LinkNode//往头部插入节点snode=&LinkNode{Data:6,}sl.InsertByHead(snode)sl.Print()fmt.Println("===============================")//往尾部插入节点snode=&LinkNode{Data:5,}sl.InsertByTail(snode)sl.Print()fmt.Println("===============================")//查询下标为2的节点node:=sl.Search(2)fmt.Println("Node2:",node.Data)fmt.Println("===============================")//删除下标为2的节点sl.DeleteByIndex(2)sl.Print()fmt.Println("===============================")//删除Data为3的节点sl.DeleteByData(3)sl.Print()}