单向链表

目前创新互联公司已为上千的企业提供了网站建设、域名、虚拟空间、网站改版维护、企业网站设计、泉山网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

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

特点：

(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()
}

文章名称：golang实现单向链表的方法
文章出自：http://scgulin.cn/article/gdpohj.html