简介
单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成是元素加指针。
思路
为了能够兼容所有类型，采用空接口。为了更好的封装，用"私有"的next和insert、remove等，看下方详细解释。
节点结构体
属性
type ListNode struct { Val interface{} next *ListNode lst *SingleList }
- Val：节点的值
- next：下一节点指针
- lst：所属单链表
Val采用空接口，接收任意数据类型，可通过类型断言再赋给对应类型。
方法
返回下一个节点，O(1)
func (node *ListNode)Next() *ListNode { return node.next }
主要用于遍历，我在其他方法中也有调用。
单链表结构体
属性
type SingleList struct { head *ListNode len int }
- head：头结点
- len：单链表长度
这里其实可以将head的Val用来存储长度，可以稍微节省一点内存，由于还需要类型断言，比较麻烦，就算了
方法
Init
func (lst *SingleList)Init(){ lst.head = new(ListNode) lst.head.lst = lst lst.len = 0 }
创建头结点，长度为0，O(1)
New
func New() *SingleList { lst := new(SingleList) lst.Init() return lst }
返回创建的单链表，调用了Init，O(1)
Clear
func (lst *SingleList)Clear(){ lst.Init() }
调用Init，利用Go自己的垃圾回收，O(1)
Len
func (lst *SingleList)Len() int { return lst.len }
返回单链表长度，O(1)
Front
func (lst *SingleList)Front() *ListNode { return lst.head.Next() }
Back
func (lst *SingleList)Back() *ListNode { if lst.len == 0{ return nil } cur := lst.head.Next() for{ if cur.Next() == nil{ return cur } cur = cur.Next() } }
返回最后一个节点，空链表的情况下为nil，O(n)
insert
func (lst *SingleList)insert(e, at *ListNode) *ListNode{ lst.len++ e.next = at.next at.next = e e.lst = lst return e }
返回指向插入的节点e的指针。
- e：待插入节点
- at：链表
仅在此函数进行长度增加，其他插入函数调用此函数，O(1)。
InsertAfter
1.func (lst *SingleList)InsertAfter(val interface{}, mark *ListNode) *ListNode { if mark == nil{ return nil } if mark.lst == lst{ return lst.insert(&ListNode{Val:val},mark) } return nil }
生成值为val的节点，并插入链表节点mark后，返回插入的节点，mark为nil或不属于单链表的情况下，返回nil。调用了insert，O(1)
- val：待插节点值
- mark：在此节点后插入，如果此节点属于单链表lst
PushBack
func (lst *SingleList)PushBack(val interface{}) *ListNode{ end := lst.Back() if end == nil{ return lst.InsertAfter(val,lst.head) }else { return lst.InsertAfter(val,end) } }
生成值为val的节点，并插入链表尾节点后，调用Back和InsertAfter。返回指向生成节点的指针，O(n)。
- val:待插节点值
PushFront
func (lst *SingleList)PushFront(val interface{}) *ListNode { return lst.InsertAfter(val,lst.head) }
生成值为val的节点，并插入链表头节点后，调用InsertAfter。返回指向生成节点的指针，O(1)。
- val:待插节点值
remove
func (lst *SingleList)remove(e *ListNode) *ListNode{ nextOne := e.next if nextOne == nil{ return nil } lst.len-- e.next = e.next.next nextOne.lst = nil return nextOne }
删除e的下一个节点，返回删除的节点，仅在此函数进行长度减少，其他删除函数调用此函数。e是尾节点时返回nil，O(1)。
- e：单链表上的节点，需删除它后面的一个节点
RemoveAfter
func (lst *SingleList)RemoveAfter(e *ListNode) *ListNode{ if e == nil{ return nil } if e.lst == lst{ return lst.remove(e) } return nil }
删除指定节点的后一个节点，返回删除的节点，指定元素为尾节点或nil时，返回nil，O(1)
RemoveFront
func (lst *SingleList)RemoveFront() *ListNode { return lst.remove(lst.head) }
测试
常见问题
怎么遍历呀？
像下面这样就可以了呦
for e := lst.Front(); e != nil; e = e.Next() { do something with e.Val }
全部代码
具体代码和测试代码在：https://gitee.com/frankyu365/datastructure
参考
更多Go相关内容：Go-Golang学习总结笔记
有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。
