第一节 如何用Go实现单链表
一、概念介绍
下面这副图是我们单链表运煤车队。
每节运煤车就是单链表里的元素，每节车厢里的煤炭就是元素中保存的数据。前后车通过锁链相连，作为单链表运煤车，从1号车厢开始，每节车厢都知道后面拉着哪一节车厢，却不知道前面是哪节车厢拉的自己。第一节车厢没有任何车厢拉它，我们就叫它车头，第五节车厢后面拉其他车厢，我们称为车尾。
作为单链表它最大的特点就是能随意增加车队的长度，也能随意减少车队的长度。这是比数组公交车最大的优点。
二、go语言实现讲解
1、节点
每节车厢都由车体、绳索和煤炭构成。在go语言中表示这种自定义组合体的类型就是结构，当然为了通用性，我们这里要把车厢转换成节点也就是元素，煤炭转换成数据，绳索转换成指针。
type node struct {
data object
next *node
}
用张图来描述这种对应关系。
这里结构体node表示车厢，data表示煤炭用object类型，next是牵着下节车厢的绳索，用指针表示。
对于车厢来说，除了放煤炭外，还能放瓜果、衣物、饭菜等等，所以这里data的类型必须通用，当然go里是没有java里的object类型的，所以我们就自己定义了一个。
type object interface{}
2、链表
光有车厢还不够，我们还要描述车厢组成的车队。每个单链表车队都有车头、车尾和车厢数量，我们同样以结构来表现。
type list struct {
size uint64 // 车辆数量
head *node // 车头
tail *node // 车尾
}
3、方法
（1）初始化
第一步就是组装单链表车队，这就是初始化。不过开始的时候车队是个空壳，一个车厢没有。
func (list *list) init() {
(*list).size = 0 // 此时链表是空的
(*list).head = nil // 没有车头
(*list).tail = nil // 没有车尾
}
（2）添加元素
当前的单链表是空的，所以我们要向里面添加元素。
func (list *list) append(node *node) {
(*list).head = node // 这是单链表的第一个元素，也是链表的头部
(*list).tail = node // 同时是单链表的尾部
(*list).size = 1 // 单链表有了第一个元素
}
现在单链表有了第一个元素，我还想再添加一个元素，当然是添加到单链表尾部。
func (list *list) append(node *node) {
if (*list).size == 0 { // 无元素的时候添加
(*list).head = node // 这是单链表的第一个元素，也是链表的头部
(*list).tail = node // 同时是单链表的尾部
(*list).size = 1 // 单链表有了第一个元素
} else { // 有元素了再添加
oldtail := (*list).tail
(*oldtail).next = node // node放到尾部元素后面
(*list).tail = node // node成为新的尾部
(*list).size++ // 元素数量增加
}
}
分析上面的代码存在3处疑点，元芳你怎么看？属下认为
第一，node如果为空，则添加无任何意义；
第二，代码中存在重复的地方；
这第三么，卑职如何才能知道新增结果？
下面大卫哥顺着元芳的思路改进下代码。
func (list *list) append(node *node) bool {
if node == nil {
return false
}
(*node).next = nil
// 将新元素放入单链表中
if (*list).size == 0 {
(*list).head = node
} else {
oldtail := (*list).tail
(*oldtail).next = node
}
// 调整尾部位置，及链表元素数量
(*list).tail = node // node成为新的尾部
(*list).size++ // 元素数量增加
return true
}
（3）插入元素
一天领导让大卫哥把他小舅子安排到第一个，于是大卫哥为了拍好领导马屁。绞尽脑汁弄了一个方法。
func (list *list) insert(node *node) bool {
if node == nil {
return false
}
(*node).next = (*list).head // 领导小舅子排到之前第一名前面
(*list).head = node // 领导小舅子成为第一名
(*list).size++
return true
}
来托关系插队的人越来越多，领导的关系户不能动，只能插后面人的队了。于是大卫哥又修改了代码，增加了位置参数。
func (list *list) insert(i uint,node *node) bool {
// 空的节点、索引超出范围和空链表都无法做插入操作
if node == nil || i > (*list).size || (*list).size == 0 {
return false
}
if i == 0 { // 直接排第一，也就领导小舅子才可以
(*node).next = (*list).head
(*list).head = node
} else {
// 找到前一个元素
preitem := (*list).head
for j := 1 ; j < i; j++ { // 数前面i个元素
preitem = (*preitem).next
}
// 原来元素放到新元素后面,新元素放到前一个元素后面
(*node).next = (*preitem).next
(*preitem).next = preitem
}
(*list).size++
return true
}
（4）删除元素
插队的关系户太多，影响了正常排队的人，被人投诉，大卫哥只好想办法删除一些。
func (list *list) remove(i uint, node *node) bool {
if i >= (*list).size {
return false
}
if i == 0 { // 删除头部
node = (*list).head
(*list).head = (*node).next
if (*list).size == 1 { // 如果只有一个元素，那尾部也要调整
(*list).tail = nil
}
} else {
preitem := (*list).head
for j := 1; j < i; j++ {
preitem = (*preitem).next
}
node = (*preitem).next
(*preitem).next = (*node).next
if i == ((*list).size - 1) { // 若删除的尾部，尾部指针需要调整
(*list).tail = preitem
}
}
(*list).size--
return true
}
（5）获取
为了获取某个位置的元素，我们需要一个方法。
func (list *list) get(i uint) *node {
if i >= (*list).size {
return nil
}
item := (*list).head
for j := 0; j < i ; j++ { // 从head数i个
item = (*item).next
}
return item
}
到这里基本框架已经出来了，不过还有几个接口还没实现，作为课后作业。
三、小结
单链表就和列车类似，一个接着一个，所以本节从列车类比介绍了单链表的go语言实现。在接口实现部分大卫哥以序号作为链表中每个节点的操作关键字。在实际应用中，我们往往以data中的某一个字段作为操作关键字。所以这也衍生出链表的不同接口，大家可以参考大卫哥留的链接中的代码实现作为理解。同时有些实现将表头独立出来并不存放数据，这在一定程度上简化了代码的实现。
四、习题
（1）补全getsize,removeall,gethead和gettail的定义和实现。
（2）以data作为参数，考虑单链表的实现。
（3）将单链表的head独立出来，此时的head是独立的，不存放data，如下图，考虑单链表的实现，并比较这种实现。
（4）如果将head和tail都独立出来，都不存放data，此时的单链表如何实现？这样实现的代码在插入删除操作时候是不是更容易点？