golang實現單向鏈表的方法

單向鏈表

單向鏈表(單鏈表)是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始;鏈表是使用指針進行構造的列表;又稱為結點列表，因為鏈表是由一個個結點組裝起來的;其中每個結點都有指針成員變量指向列表中的下一個結點;

特點：

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