Go语言实现数据结构（一）单链表

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

1.基本释义

2.结构体设计

3.基本方法设计

4.Main函数测试

1. 基本释义

　　线性表包含两种存储方法：顺序存储结构和链式存储结构，其中顺序表的缺点是不便插入与删除数据；接下来我们重点实现基于Go语言的链式存储线性表。

2. 结构体设计

　　每个结点包含两部分：数据域+指针域，上一个结点的指针指向下一结点，首尾相连，形成链表。特别注意的是每个链表必须包含头结点（数据域为空）；

//导入包
package main
import "fmt"

//创建 结点 结构体
type Node struct{
	Data interface{}
	Next *Node               //  Next = &Node
}
//链表 结构体
type LList struct{
	Head *Node
	Length int
}

3. 基本方法设计

　　在创建完链表后，我们将实现链表的基本操作和辅助操作，基本操作指的是（新增）插入数据、删除数据、查找数据、求链表长度；而辅助操作指的是创建结点、创建（初始化）链表、判断是否为空链表，此处和其他语言不同之处是Go语言具有垃圾自动回收的特性，因此不需要释放指针或内存，后续没有用到的变量Go语言会自动回收。

a.设计接口

type Method interface {
	Insert(i int,v interface{})            //增
	Delete(i int)                          //删
	GetLength() int                        //getLength
	Search(v interface{}) int              //查
	isNull()bool                           //判断链表是否为空
}

b.设计初始化函数

//创建结点
func CreateNode(v interface{})*Node{
	return &Node{v,nil}
}
//创建空链表
func CreateList()*LList{
	return &LList{CreateNode(nil),0}
}

c.基于链表结构体 LList 实现接口 Method 中的基本方法

//在i处插入节点（前插）
func (list *LList)Insert(i int,v interface{}){
	s := CreateNode(v)  //*Node
	pre := list.Head  //*Node
	for count:=0;count<=i-1;count++{
		if count == i-1{
			s.Next = pre.Next
			pre.Next = s
			list.Length++
		}
		pre = pre.Next

	}
}
//删除i处节点
func (list *LList)Delete(i int){
	pre := list.Head
	for count:=0;count<=i-1;count++{
		s := pre.Next
		if count == i-1{
			pre.Next = s.Next
			list.Length--
		}
		pre = pre.Next
	}
}
//返回链表长度
func (list *LList)GetLength() int{
	pre := list.Head
	for pre.Next!=nil{
		list.Length++
	}
	return list.Length
}
//查值v所在位置
func (list *LList)Search(v interface{}) int{
	pre := list.Head.Next
	for i:=1;i<=list.Length;i++{
		if pre.Data == v{
			return i
		}
		pre = pre.Next
	}
	return 0
}
//判空
func (list *LList) isNull() bool{
	pre := list.Head.Next
	if pre == nil{
		return true
	}
	return false
}

d.设计链表打印输出函数

//打印链表
func PrintList(list *LList){
	pre := list.Head  //*Node
	fmt.Println("LList shows as follow:...")
	for i:=0;i<=list.Length;i++{
    	fmt.Printf( "%v\n",pre)
		pre  = pre.Next
	}
}

4.Main函数测试

func main(){
	lList := CreateList()
	//fmt.Println("List is Null:",lList.isNull())
	var M Method
	M = lList
	M.Insert(1,3)
	M.Insert(2,6)
	M.Insert(1,5)
	PrintList(lList)
	fmt.Println("List length is:",lList.Length)
	fmt.Println("元素6在位置  ",M.Search(6))
	fmt.Println("元素100在位置  ",M.Search(100))
	fmt.Println("List is Null:",lList.isNull())
	M.Delete(2)
	PrintList(lList)
	fmt.Println("List length is:",lList.Length)
}