大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
单向链表
目前创新互联公司已为上千的企业提供了网站建设、域名、虚拟空间、网站改版维护、企业网站设计、泉山网站维护等服务,公司将坚持客户导向、应用为本的策略,正道将秉承"和谐、参与、激情"的文化,与客户和合作伙伴齐心协力一起成长,共同发展。
单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
特点:
(1)单个结点创建非常方便,普通的线性内存通常在创建的时候就需要设定数据的大小
(2)结点的删除非常方便,不需要像线性结构那样移动剩下的数据
(3)结点的访问方便,可以通过循环或者递归的方法访问到任意数据,但是平均的访问效率低于线性表
package main import ( "fmt" ) type LinkNode struct { Data interface{} Next *LinkNode } type SingleLink struct { head *LinkNode tail *LinkNode size int } // 初始化链表 func InitSingleLink()(*SingleLink){ return &SingleLink{ head:nil, tail:nil, size:0, } } // 获取头部节点 func (sl *SingleLink)GetHead()*LinkNode{ return sl.head } // 获取尾部节点 func (sl *SingleLink)GetTail()*LinkNode{ return sl.tail } // 打印链表 func (sl *SingleLink) Print(){ fmt.Println("SingleLink size:",sl.Length()) if sl.size == 0{ return } ptr := sl.GetHead() for ptr != nil{ fmt.Println("Data:",ptr.Data) ptr = ptr.Next } } //链表长度 func (sl *SingleLink) Length() int{ return sl.size } //插入数据(头插) func (sl *SingleLink) InsertByHead(node *LinkNode){ if node == nil{ return } // 判断是否第一个节点 if sl.Length() == 0{ sl.head = node sl.tail = node node.Next = nil }else{ oldHeadNode := sl.GetHead() sl.head = node sl.head.Next = oldHeadNode } sl.size++ } //插入数据(尾插) func (sl *SingleLink) InsertByTail(node *LinkNode) { if node == nil{ return } // 插入第一个节点 if sl.size == 0{ sl.head = node sl.tail = node node.Next = nil }else{ sl.tail.Next = node node.Next = nil sl.tail = node } sl.size ++ } //插入数据(下标)位置 func (sl *SingleLink) InsertByIndex(index int, node *LinkNode){ if node == nil{ return } // 往头部插入 if index == 0 { sl.InsertByHead(node) }else{ if index > sl.Length(){ return }else if index == sl.Length(){ //往尾部添加节点 sl.InsertByTail(node) }else{ preNode := sl.Search(index-1) // 下标为 index 的上一个节点 currentNode := sl.Search(index) // 下标为 index 的节点 preNode.Next = node node.Next = currentNode sl.size++ } } } //删除数据(下标)位置 func (sl *SingleLink) DeleteByIndex(index int) { if sl.Length() == 0 || index > sl.Length(){ return } // 删除第一个节点 if index == 0{ sl.head = sl.head.Next }else{ preNode := sl.Search(index-1) if index != sl.Length()-1{ nextNode := sl.Search(index).Next preNode.Next = nextNode }else{ sl.tail = preNode preNode.Next = nil } } sl.size-- } // 删除数据(数据) func (sl *SingleLink) DeleteByData(Data interface{}) { if sl.Length() == 0 || Data == nil{ return } node := sl.head preNode := sl.head for node.Next != nil{ preNode = node node = node.Next if node.Data.(int) == Data.(int){ preNode.Next = node.Next node.Next = nil node.Data = nil node = nil return } } } // 查询数据 func (sl *SingleLink) Search(index int)(node *LinkNode) { if sl.Length() == 0 || index > sl.Length(){ return nil } // 是否头部节点 if index == 0{ return sl.GetHead() } node = sl.head for i:=0;i<=index;i++{ node = node.Next } return } //销毁链表 func (sl *SingleLink) Destroy() { sl.tail = nil sl.head = nil sl.size = 0 } func main() { // 初始化链表 sl := InitSingleLink() // 指定指标插入 for i:=0;i<5;i++{ snode := &LinkNode{ Data:i, } sl.InsertByIndex(i,snode) } sl.Print() fmt.Println("===============================") var snode *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() }