自己动手用golang实现单向链表

单向链表

特点:

1、Head 节点 上一个节点为空

2、Tail 节点下一个节点为空

3、除Tail节点外,每个节点连接到下一个节点

image.png

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

本文来自:51CTO博客

感谢作者:筑梦攻城狮

查看原文:自己动手用golang实现单向链表

• 编辑
• 预览