[数据结构与算法]单链表的创建、插入、删除、遍历的Go实现

package main

import (
	"errors"
	"fmt"
)

/*
带头结点的单链表

*/

type Node struct {
	key int
	value string
	next * Node
}

//创建一个链表
func newList()(head *Node) {
	head = &Node {
		next: nil,
	}
	return
}

//头插法
func addHeadList(head, newNode *Node) {
	if head.next == nil {//链表为空的时候
		head.next = newNode
	}else {
		newNode.next = head.next
		head.next = newNode
	}
}

//尾插法
func addTailList(head, newNode *Node) {
	//if head.next == nil {
	//	head.next = newNode
	//} else {
		tmp := head
		for ;tmp.next != nil; tmp = tmp.next {

		}
		tmp.next = newNode
	//}
}

//按key查找
func findNodebyKey(head *Node, key int)(keyNode *Node, err error) {
	if head.next == nil {
		fmt.Println("链表为空")
		return
	}
	flag := false
	tmp := head
	for tmp.next != nil {
		if  tmp.next.key == key {
			keyNode = tmp.next
			flag = true
		}
		tmp = tmp.next
	}
	if !flag {
		err = errors.New("链表中找不到该key对应的Node")
	}
	return

}

//按位置查找  0代表头结点
func findNodeByLocation(head *Node, seat int) (seatNode *Node, err error){
	if head.next == nil {
		err = errors.New("链表为空")
		return
	}
	if seat < 1 {
		err = errors.New("传入的位置有误，请重新操作")
		return
	}
	tmp := head
	i := 1
	for tmp.next != nil {

		if i == seat {
			seatNode = tmp.next
			return
		}
		i++
		tmp = tmp.next
	}

	//链表没那么长的情况
	err = errors.New(fmt.Sprintf("链表的长度为：%d,小于你输入的位置:%d",i-1,seat))
	return


}

//按位置插入
//下一个位置等于seat
func insertByLocation(head,insertNode *Node,seat int) (err error){
	if head.next == nil {
		err = errors.New("链表为空")
		return
	}
	if seat <1 {
		err = errors.New("传入seat参数有误，请重新操作")
		return
	}

	tmp := head
	if seat == 1{
		insertNode.next = tmp.next
		tmp.next = insertNode
		return
	}
	i :=0
	for tmp.next != nil {
		if i == seat-1 {
			//插入结点
			insertNode.next =tmp.next
			tmp.next = insertNode
			return
		}
		tmp = tmp.next
		i++
	}
	if i+1 == seat {
		tmp.next = insertNode
		return
	}

	//链表没那么长的情况
	err = errors.New(fmt.Sprintf("链表的长度为：%d,你要插入的位置:%d",i,seat))
	return
}

//按位置删除
func delByLocation(head *Node,seat int) (err error) {
	if seat <1 {
		err = errors.New("输入的位置有误")
		return
	}
	if head.next == nil {
		err = errors.New("链表为空")
		return
	}
	tmp := head
	i :=0

	for tmp.next != nil {
		if i == seat -1 { //找到要删除位置的前一个
			tmp.next = tmp.next.next //跳过下一个
			return
		}
		i++
		fmt.Printf("------i:%d------\n",i)
		tmp = tmp.next
	}
	err = errors.New(fmt.Sprintf(">>>链表的长度为：%d,你要删除的位置为:%d<<<\n",i,seat))
	return

}


//按顺序插入
func addByOrder(head,newNode *Node) {
	if head.next == nil {
		head.next = newNode
		return
	}
	//找到第一个比他大的，在前一个位置插入
	tmp := head
	for tmp.next != nil {
		if tmp.next.key > newNode.key {
			newNode.next = tmp.next
			tmp.next = newNode
			//找到并且插入完毕，退出
			return
		}
		tmp = tmp.next
	}
	//找不到比他大的情况
	tmp.next = newNode


}


//遍历的方法
func showList(head *Node) {
	if head.next == nil {
		fmt.Println("链表为空")
		return
	}
	tmp := head
	for  tmp.next != nil {
		tmp = tmp.next
		fmt.Printf("key:%d,value:%s>>>",tmp.key,tmp.value)

	}
	fmt.Println()
}

func main() {
	fmt.Println("come in main()----list")
	defer fmt.Println("out of main()---list")
	head := newList()
	node1 := &Node{
		value: "1111",
		key:1,
	}
	node2 := &Node {
		value: "2222",
		key:2,
	}

	node3 := &Node{
		value: "3333",
		key:3,
	}

	node4 := &Node {
		value :"44444",
		key:4,
	}
	node5 := &Node {
		value :"5555",
		key:5,
	}
	//addHeadList(head,node1)
	//addHeadList(head,node2)
	//addHeadList(head,node3)
	addTailList(head,node1)
	addTailList(head,node2)
	addTailList(head,node3)

	addByOrder(head,node5)
	addByOrder(head,node4)

	showList(head)
	node , err :=findNodebyKey(head,1)
	if err != nil {
		fmt.Println("err :",err)
		return
	}
	fmt.Printf("node:%#v\n",node)

	seatNode, err := findNodeByLocation(head,5)
	if err != nil {
		fmt.Println("err :",err)
		return
	}
	fmt.Printf("seatNode:%#v\n",seatNode)

	//nodeTest := &Node{
	//	key: 6666,
	//	value: "66666",
	//}
	//err =insertByLocation(head,nodeTest,7)
	err = delByLocation(head,6)
	if err != nil {
		fmt.Println(">>>>>>>>>err :",err)
		return
	}
	fmt.Println("------------------------")
	showList(head)
}