【go寫資料結構】 線性表-連結串列實現

git地址：https://gitee.com/HappyTeemo/go_for_algorithm

package my_list

import (
	"fmt"
)

//鏈式儲存
//可以用頭指標用來儲存長度 也就是第0個
//但是這個有個弊端就是當儲存的不是int型別時會有問題
//所有還是新增一個欄位表示長度
//為了保持從1開始，頭指標還是不放東西
type LinkList struct {
	Head   *Node
	Length int
}

type Node struct {
	Data ElemType
	Next *Node
}

//初始化列表
func (l *LinkList) InitList() {
	l.Head = new(Node)
	l.Length = 0
}

//清空列表（不會清除頭結點）
func (l *LinkList) ClearList() {
	p := new(Node)
	q := l.Head //q指向第一個結點

	//釋放記憶體，其實go可以不需要這個迴圈
	for q != nil {
		p = q
		q = p.Next
		p = nil
	}
	l.Head.Next = nil
	l.Length = 0
}

//判斷是否為空
func (l *LinkList) ListEmpty() bool {
	if l.Length == 0 {
		return true
	}
	return false
}

//獲取長度
func (l *LinkList) ListLength() int {
	return l.Length
}

//查
func (l *LinkList) GetElem(index int, e *ElemType) bool {
	if l.Length == 0 {
		fmt.Println("獲取失敗，佇列為空")
		return false
	}
	if index < 1 || index > l.Length {
		fmt.Println("獲取失敗，位置錯誤")
		return false
	}

	j := 1
	q := l.Head.Next
	for q != nil && j < index {
		q = q.Next
		j++
	}

	//有了這一步其實開頭的判斷可以去掉
	if q == nil || j > index {
		return false
	}

	*e = q.Data
	return true
}

//按照元素進行查詢，獲取索引
func (l *LinkList) LocateElem(value ElemType) int {

	if l.Length == 0 {
		fmt.Println("獲取失敗，佇列為空")
		return 0
	}

	j := 0
	q := l.Head.Next
	for q != nil {
		j++
		if q.Data == value {
			break
		}
		q = q.Next
	}

	if j >= MAXSIZE {
		return 0
	}

	return j
}

//按照索引進行插入資料
func (l *LinkList) ListInsert(index int, value ElemType) bool {

	if l.Length == MAXSIZE { //滿了
		fmt.Println("插入失敗，佇列已滿")
		return false
	}
	if index < 1 || index > l.Length+1 {
		fmt.Println("插入失敗，位置錯誤")
		return false
	}

	front := l.Head

	//找到插入位置的前驅
	for j := 1; j < index; j++ {
		front = front.Next
	}

	//新建節點，加入連結串列
	n := new(Node)
	n.Next = front.Next
	n.Data = value
	front.Next = n

	l.Length++

	return true
}

//刪
func (l *LinkList) ListDelete(index int, e *ElemType) bool {
	if l.Length == 0 {
		fmt.Println("獲取失敗，佇列為空")
		return false
	}
	if index < 1 || index > l.Length {
		fmt.Println("獲取失敗，位置錯誤")
		return false
	}

	j := 1
	front := l.Head

	//找到索引的直接前驅
	for front.Next != nil && j < index {
		front = front.Next
		j++
	}

	if front.Next == nil || j > index {
		return false
	}

	//開始刪除
	tmp := front.Next     //記錄要刪除的
	*e = tmp.Data         //返回刪除節點的資料
	front.Next = tmp.Next //前驅節點直接指向後繼節點，就跳過了要刪除的節點
	//free(tmp)

	l.Length--

	return true
}

//輸出
func (l *LinkList) Echo() {
	//遍歷的寫法
	curItem := l.Head.Next
	for i := 0; i < l.Length; i++ {
		fmt.Print(curItem.Data, " ")
		curItem = curItem.Next
	}
	fmt.Println()
}

func (l *LinkList) Test() {
	fmt.Println("測試開始")

	my_list := new(LinkList)
	my_list.InitList()

	for i := 1; i <= 10; i++ {
		my_list.ListInsert(i, ElemType(i*i+1))
		my_list.Echo()
	}

	fmt.Println("第5個這裡插入256")
	my_list.ListInsert(5, 256)
	my_list.Echo()
	my_list.ListInsert(199, 99)

	var e ElemType

	my_list.ListDelete(1, &e)
	fmt.Println("刪除頭元素:", e)
	my_list.Echo()

	my_list.ListDelete(my_list.ListLength(), &e)
	fmt.Println("刪除尾元素:", e)
	my_list.Echo()

	my_list.GetElem(6, &e)
	fmt.Println("獲取第6個:", e)

	fmt.Println("256的位置:", my_list.LocateElem(256))

	fmt.Println("長度：", my_list.ListLength())

	fmt.Println("開始清空")
	my_list.ClearList()
	if my_list.ListEmpty() {
		fmt.Println("已清空")
		my_list.Echo()
	}

	//fmt.Println("準備合併")
	//
	//my_list_a := new(SqList)
	//my_list_b := new(SqList)
	//for i := 1; i <= 10; i++ {
	//	my_list_a.ListInsert(i, ElemType(2*i+1))
	//	my_list_b.ListInsert(i, ElemType(3*i+1))
	//}
	//
	//my_list_a.Echo()
	//my_list_b.Echo()
	//
	//fmt.Println("合併後")
	//
	//my_list_a.UnionL(my_list_b)
	//my_list_a.Echo()

	fmt.Println("測試完成")
}