链表指的是存储结构是链式的。指每一个结点除了本身数据之外，还有一个指针指向了下一个结点的地址。就像火车车厢，车厢本身是数据，车钩链接着下一个车厢。
链表有单链表，双链表，循环链表结构，本节只介绍最简单的单链表
单链表定义：
type Student struct {
Name string //字段，也就是本身的数据，可以有多个字段
Next* Student //指向自己的指针字段
}
例：
type Student struct {
Age int
Name string
Next *People
} //定义包含两个字段一个指针字段的Student的数据类型，为了好理解先定义了一个指向另一个数据类型的指针
type People struct {
Age int
Name string
}
func testList() {
//手动构造两个节点
var s Student //定义Student类型的变量s
s.Age = 100 //给变量赋值
s.Name = "abc"
/*s.Next = &People{
Age:100,
Name:"efg",
}*/ //这个注释跟下面三行内容一样的效果。就是给s.Next分配指向People类型的内存地址，并初始化
s.Next = new(People)
s.Next.Age = 1000
s.Next.Name = "efg"
fmt.Printf("list header:%#v
", s)
fmt.Printf("data:%#v
", *(s.Next))
}
//输出结果
list header:main.Student{Age:100, Name:"abc", Next:(*main.People)(0xc0420023e0)}
data:main.People{Age:1000, Name:"efg"}
上面构造了两个节点，如下图所示：
下面我们在People类型里再添加一个指针，指向Student类型
type Student struct{
Age int
Name string
Next *People
}
type People struct {
Age int
Name string
Next *Student //添加一个指向Student类型的指针
}
func testList(){
var s Student //第一个结点
s.Age = 100
s.Name = "abc"
s.Next = new(People) //第二个结点
// s.Next = &People{
// Age:100,
// Name:"efg",
// }
s.Next.Age = 1000
s.Next.Name = "efg"
s.Next.Next = new(Student) //第三个结点
s.Next.Next.Age = 100
s.Next.Next.Name = "xyz"
fmt.Printf("list header:%#v
", s) //打印第一个结点的信息
fmt.Printf("data:%#v
", *(s.Next)) //打印第二个结点信息
fmt.Printf("data:%#v
", *(s.Next.Next)) //打印第三个节点的信息
fmt.Printf("data:%#v
", s.Next.Next.Next) //打钱第三个节点指针的地址
}
//输出结果：
list header:main.Student{Age:100, Name:"abc", Next:(*main.People)(0xc0420443a0)}
data:main.People{Age:1000, Name:"efg", Next:(*main.Student)(0xc0420443c0)}
data:main.Student{Age:100, Name:"xyz", Next:(*main.People)(nil)}
data:(*main.People)(nil)
现在构造了三个结点，如下图所示：
上面构造节点的方法慢，且逻辑复杂，而且指针是指向了另一种数据结构类型的，需要对它进行抽象。也就是说需要利用模板来生成结点。而且生成一个指向自己的指针，来构造链表。
上面的方法是手动构造了三个节点的链表，下面利用函数来动态的生成结点。
type Teacher struct{ //定义链表的存储结构
Name string
Age int
Next *Teacher
}
func createInHeader(h *Teacher, name string, age int) (*Teacher) {
//这个函数的主要作用是生成一个新的结点，并且把头部结点的指针的值赋值给新的结点，并且返回这个这个结点的内存地址，再把这个新的结点的内存地址赋值给头部结点
p := &Teacher{} //相当于 var p *Teacher p = &Teacher{},申明变量，并分配一个内存地址
p.Age = age //字段属性赋值
p.Name = name
p.Next = h //把头结点指针的值赋值给新结点
return p //返回新节点的地址
}
func printList(h *Teacher){
for h != nil{
fmt.Printf("Name:%v Age:%v
",h.Name,h.Age)
h = h.Next //后移一个节点
}
}
func testCreateInHeader() {
var header *Teacher //定义一个指针变量
header = createInHeader(header, "a", 18) //header指向第一个生成的结点
header = createInHeader(header, "b", 19) //header指向第二个生成的结点
header = createInHeader(header, "c", 20) //header指向第三个生成的结点
printList(header)
}
//输出结果
Name:c Age:20
Name:b Age:19
Name:a Age:18
上面动态生成三个结点，每次相当于前插，就是header指针变量每次都指向最新生成的那个结点。上面构造的三个节点的链式存储结构为：
下面演示从最后插入：
type Teacher struct{
Name string
Age int
Next *Teacher
}
func printList(h *Teacher){
for h != nil{
fmt.Printf("Name:%v Age:%v
",h.Name,h.Age)
h = h.Next
}
}
func createInTail(tail *Teacher, name string, age int) (*Teacher) {
//生成新的结点，并把新生成的节点的地址返回给尾指针变量。尾指针变量永远指向最后一个结点。
p := &Teacher{}
p.Age = age
p.Name = name
if tail == nil { //如果一开始没有节点，则直接返回新生成的结点的地址给尾指针变量
return p
}
tail.Next = p //假设已经有了一个节点，那么tail != nil,则一行表示把原尾结点的指针指向新生成的结点
return p //返回新生成结点的地址
}
func testCreateInTail() {
var header *Teacher
var tail *Teacher
tail = createInTail(tail, "a", 18)
if header == nil {
header = tail //生成第一个节点时，header也指向了第一个节点
}
tail = createInTail(tail, "b", 19)//尾指针永远指向新生成的结点
tail = createInTail(tail, "c", 20)
printList(header)
}
//输出结果是：
Name:a Age:18
Name:b Age:19
Name:c Age:20
上面构造的节点的链式存储结构为：
