golang實(shí)現(xiàn)單向鏈表的方法

單向鏈表

單向鏈表(單鏈表)是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪問(wèn)要通過(guò)順序讀取從頭部開(kāi)始;鏈表是使用指針進(jìn)行構(gòu)造的列表;又稱為結(jié)點(diǎn)列表，因?yàn)殒湵硎怯梢粋€(gè)個(gè)結(jié)點(diǎn)組裝起來(lái)的;其中每個(gè)結(jié)點(diǎn)都有指針成員變量指向列表中的下一個(gè)結(jié)點(diǎn);

特點(diǎn)：

(1)單個(gè)結(jié)點(diǎn)創(chuàng)建非常方便，普通的線性內(nèi)存通常在創(chuàng)建的時(shí)候就需要設(shè)定數(shù)據(jù)的大小

(2)結(jié)點(diǎn)的刪除非常方便，不需要像線性結(jié)構(gòu)那樣移動(dòng)剩下的數(shù)據(jù)

(3)結(jié)點(diǎn)的訪問(wèn)方便，可以通過(guò)循環(huán)或者遞歸的方法訪問(wèn)到任意數(shù)據(jù)，但是平均的訪問(wèn)效率低于線性表

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,
   }
}

// 獲取頭部節(jié)點(diǎn)
func (sl *SingleLink)GetHead()*LinkNode{
   return  sl.head
}

// 獲取尾部節(jié)點(diǎn)
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
   }
}

//鏈表長(zhǎng)度
func (sl *SingleLink) Length() int{
   return sl.size
}

//插入數(shù)據(jù)（頭插）
func (sl *SingleLink) InsertByHead(node *LinkNode){
   if node == nil{
      return
   }
   // 判斷是否第一個(gè)節(jié)點(diǎn)
   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++
}

//插入數(shù)據(jù)（尾插）
func (sl *SingleLink) InsertByTail(node *LinkNode) {
   if node == nil{
      return
   }
   // 插入第一個(gè)節(jié)點(diǎn)
   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 ++
}

//插入數(shù)據(jù)（下標(biāo)）位置
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(){
         //往尾部添加節(jié)點(diǎn)
         sl.InsertByTail(node)
      }else{
         preNode := sl.Search(index-1)     // 下標(biāo)為 index 的上一個(gè)節(jié)點(diǎn)
         currentNode := sl.Search(index)       // 下標(biāo)為 index 的節(jié)點(diǎn)
         preNode.Next = node
         node.Next = currentNode
         sl.size++
      }
   }
}

//刪除數(shù)據(jù)（下標(biāo)）位置
func (sl *SingleLink) DeleteByIndex(index int) {
   if sl.Length() == 0 || index > sl.Length(){
      return
   }
   // 刪除第一個(gè)節(jié)點(diǎn)
   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--
}

// 刪除數(shù)據(jù)（數(shù)據(jù)）
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
      }

   }
}

// 查詢數(shù)據(jù)
func (sl *SingleLink) Search(index int)(node *LinkNode)  {
   if     sl.Length() == 0 || index > sl.Length(){
      return nil
   }
   // 是否頭部節(jié)點(diǎn)
   if index == 0{
      return sl.GetHead()
   }
   node = sl.head
   for i:=0;i<=index;i++{
      node = node.Next
   }
   return
}

//銷(xiāo)毀鏈表
func (sl *SingleLink) Destroy() {
   sl.tail = nil
   sl.head = nil
   sl.size = 0
}

func main() {
   // 初始化鏈表
   sl := InitSingleLink()

   // 指定指標(biāo)插入
   for i:=0;i<5;i++{
      snode := &LinkNode{
         Data:i,
      }
      sl.InsertByIndex(i,snode)
   }

   sl.Print()
   fmt.Println("===============================")

   var snode *LinkNode

   // 往頭部插入節(jié)點(diǎn)
   snode = &LinkNode{
      Data:6,
   }
   sl.InsertByHead(snode)
   sl.Print()
   fmt.Println("===============================")

   //往尾部插入節(jié)點(diǎn)
   snode = &LinkNode{
      Data:5,
   }
   sl.InsertByTail(snode)

   sl.Print()
   fmt.Println("===============================")

   // 查詢下標(biāo)為2的節(jié)點(diǎn)
   node := sl.Search(2)
   fmt.Println("Node2:",node.Data)
   fmt.Println("===============================")
   // 刪除下標(biāo)為2的節(jié)點(diǎn)
   sl.DeleteByIndex(2)
   sl.Print()
   fmt.Println("===============================")

   // 刪除Data 為3的節(jié)點(diǎn)
   sl.DeleteByData(3)
   sl.Print()
}