GO语言 链表（单向链表

链表的前提

GO语言的链表类似于C语言的链表，它通过结构体和结构体指针实现。

结构体

GO语言定义结构体如下
 

type user struct {
	name string
	age  int
	next *user
}

结构体指针

结构体指针就是指向结构体的指针，我们在链表中会用到结构体指针实现链表节点之间的连接
next *user   就是结构体指针

构建链表

构建链表需要三点：头节点，尾节点，中间节点
头节点的作用相当于链表的入口，尾节点用来表示节点的结尾，中间节点用于存储信息

创建头节点
 

head := &user{}
//此时的head 类型是*user

插入节点

1.尾插法

func insert_end(head *user, name string, age int) *user {
	new_user := &user{name, age, nil}
	p := head
	for {
		if p.next != nil {
			p = p.next
		}
		break
	} //循环结束后p指向最后一个节点
	p.next = new_user
	return head
}

为什么new_user := &user{name, age, nil}创建一个结构体指针 而不是创建一个结构体变量

如果我们直接创建一个结构体变量，那它的类型就是user，由因为我们是在insert_end函数里面创建的这个变量，所以它的生命周期只有在这个函数里面存在。并且我们在接入节点的时候p.next = new_user就会报错，我们就需要改成p.next = &new_user。但是当我们的函数结束的时候new_user 就会被销毁，p.next就会指向一个已经被销毁的内存。但是我们使用new_user := &user{name, age, nil}的时候虽然user会随着函数结束而销毁但是这个内存由于被链表引用所以会一直存在。

尾插法的核心点在于寻找尾节点，并让尾节点的next指向新节点

2.头插法

func insert_head(head *user, name string, age int) *user {
	p := head.next
	new_user := &user{name, age, nil}
	head.next = new_user
	new_user.next = p
	return head
}

最后返回head是保证外部的head结构正确。我们在insert_head函数里面的head并不是main函数里面的head，他只是一个副本，我们需要副本覆盖掉原来的。所以需要return head（副本）

3.中插法（指定插入到某个节点之前）

func insert_body(head *user, name string, age int, key string) *user {
	new_user := &user{name, age, nil}
	p := head
	p2 := head.next
	for p2 != nil {
		if p2.name == key {
			p.next = new_user
			new_user.next = p2
			return head
		}
		p = p2
		p2 = p2.next
	}
	// 如果循环结束都没有找到，则输出错误信息
	fmt.Println("插入错误，没找到对应的节点")
	return head
}

在这个方法中我们需要确定当前节点的下一个节点是否是我们需要插入到它之前的节点。如果是的话就让当前节点的next指向新节点，新节点的next指向原下一节点。

链表的删除

func delete(head *user, key string) *user {
	p := head
	p2 := head.next
	for p2 != nil {
		if p2.name == key {
			p.next = p2.next
		}
		p = p2
		p2 = p2.next
	}
	return head
}

删除的主要点在于让上一节点直接指向被删除节点的next，掠过这个节点。被删除节点由于无人引用就会自动回收

链表的遍历

func bianli(head *user) {
	p := head.next
	for {
		if p != nil {
			fmt.Println(p.name, p.age)
		} else {
			break
		}
		p = p.next
	}
}

遍历只需要一个头节点，不断循环下去一直循环到nil为止，然后输出对应节点的信息