单链表是最简单的数据结构之一，它也是许多高级数据结构的基础，所以十分重要。将熟悉的数据结构用新编程语言重新实现一次，是一种有效的学习方式。下面我们用Go语言实现经典的单链表。
Go语言被誉为“21世纪的C语言”，它吸纳了C语言的众多优点，如清晰的类型体系，可以直接调用系统调用，与操作系统交互，但同时它又推陈出新，将C/C++中许多晦涩的实现简炼地重构出来。经过一段时间的学习，我能体会到Go相比于C的明显提升编程体验的方面有：
- 固定明确的代码缩进组织形式。在大规模的C/C++项目中，由于不同编码者的习惯不同，代码中存在许多不同的编码风格，给后来的阅读带来了巨大的挑战。Go语言统一了编码风格，特别是提供了Gofmt工具，实现一键排版，大幅提升了大项目的编码体验。
- 简化语言提供的方法。C/C++语言难以学习的一个重要原因是，对于同一个问题，有多种实现方法，然而多种实现方法在不同的应用场景下存在微妙的差别，编程者需要花费大量的精力去分辨学习这些差别，以换取微不足道的性能/鲁棒性提升。例如C中的i++和++i的差别，以及obj++和++obj的差别。Go作为互联网时代的C语言，摒弃了这些多样的实现方式和微妙的差异，让编程者可以集中精力解决问题，而不是纠结于语法的差异--“回字的20种写法”。
- 垃圾回收机制。C/C++让开发者最为头疼的问题之一就是资源管理问题，例如内存泄漏，虽然C++11后，智能指针的完善部分解决了这一问题，但对于广泛使用的C语言，问题依然存在。资源管理问题不仅影响软件的用户体验，还阻碍了开发者专注于解决业务问题。Go语言和绝大多数后C++语言一样，可供了完善的垃圾回收资源管理机制。
- 强大的内置数据结构。C相比于其他编程语言更难于使用的原因在于轮子的缺乏，开发者在解决业务问题之前，要自行构建大量的基础数据结构。Go语言不仅提供了数组，结构体，还内置了切片(动态数组)，键值表。除此之外，隧道，函数等都是内置的。
简要的评点了一番Go，下面动手用Go实现单链表，首先定义链表节点和链表的数据结构。Go中的局部变量可以通过返回“逃逸”出“局部”。
package kit
import (
"fmt"
"math"
)
type Val_t int
type ListNode struct {
Val Val_t
Next *ListNode
}
type List struct {
Head *ListNode
Tail *ListNode
Len int
}
func NewList() (lst *List) {
lst = &List{} //escpae once return
return
}
定义一个函数，用数组生成链表，可以看到Int2Lst()是List结构体的成员函数，但定义一个成员函数是“非侵入性”的，也就是说成员函数不用定义在结构体内，只需要将结构体作为前置参数“注入”成员函数即可。
同时，Go语言提供了便利的数组遍历方法 for..range..
func (lst *List) Ints2Lst(nums []Val_t) {
if len(nums) <= 0 {
return
}
//create a dummy node
dummy := &ListNode{Val: math.MaxInt32}
prevNode := dummy
lst.Len = 0
//create new node and link as tail
for _, n := range nums {
newNode := &ListNode{Val: n}
prevNode.Next = newNode
lst.Len++
prevNode = newNode
}
//update head and tail
if lst.Len > 0 {
lst.Head = dummy.Next
lst.Tail = prevNode
}
}
然后，添加三个函数向链表中加入元素。
/*ret node at index idx*/
func (lst *List) GetAt(idx int) *ListNode {
if idx < 0 || idx > lst.Len {
panic("index out of boundary")
}
curr := lst.Head
for idx > 0 {
curr = curr.Next
idx--
}
return curr
}
/*append node as tail*/
func (lst *List) PushBack(item Val_t) {
newNode := &ListNode{Val: item}
if lst.Len <= 0 {
lst.Head, lst.Tail = newNode, newNode
} else {
lst.Tail.Next = newNode
lst.Tail = newNode
}
lst.Len++
}
/*preppend node as head*/
func (lst *List) PushFront(item Val_t) {
newNode := &ListNode{Val: item}
if lst.Len <= 0 {
lst.Head, lst.Tail = newNode, newNode
} else {
newNode.Next = lst.Head
lst.Head = newNode
}
lst.Len++
}
/*insert node at index idx*/
func (lst *List) InsertAt(idx int, item Val_t) {
if idx < 0 || idx > lst.Len {
panic("index out of boundary")
}
newNode := &ListNode{Val: item}
//insert a node after the idx-th node
dummy := &ListNode{Val: math.MaxInt32}
dummy.Next = lst.Head
prev, next := dummy, dummy.Next
for idx > 0 {
prev = next
next = next.Next
idx--
}
prev.Next = newNode
newNode.Next = next
//update the reference of head and tail
lst.Len++
lst.Head = dummy.Next
curr := lst.Head
for curr.Next != nil {
curr = curr.Next
}
lst.Tail = curr
}
之后，添加三个函数从链表中删除元素
/*remove the tail node*/
func (lst *List) PopBack() (ret Val_t) {
if lst.Len < 1 {
panic("no item to pop")
}
ret = lst.Tail.Val
if lst.Len == 1 {
lst.Head, lst.Tail = nil, nil
} else {
prevTail := lst.Head
//move to the tail
for prevTail.Next != lst.Tail {
prevTail = prevTail.Next
}
//unlink tail node, it will be re-collected
lst.Tail = prevTail
}
lst.Len--
return
}
/*remove the head node*/
func (lst *List) PopFront() (ret Val_t) {
if lst.Len < 1 {
panic("no item to pop")
}
ret = lst.Head.Val
if lst.Len == 1 {
lst.Head, lst.Tail = nil, nil
} else {
lst.Head = lst.Head.Next
}
lst.Len--
return
}
/*remove the node at index idx*/
func (lst *List) RemoveAt(idx int) (ret Val_t) {
if idx < 0 || idx > lst.Len {
panic("index out of boundary")
}
curr := lst.GetAt(idx)
ret = curr.Val
if idx == 0 {
return lst.PopFront()
} else if idx == lst.Len-1 {
return lst.PopBack()
} else {
prev, next := lst.GetAt(idx-1), lst.GetAt(idx+1)
prev.Next = next
lst.Len--
}
return
}
再后，添加函数反转链表。Go也有类型局部函数和外部函数的概念(static和extern)，但是Go中的实现没有依赖关键字，小写字母开头的函数和变量只在包内可见，是局部的，大写字母开头的函数可以导出到包外，是外部的。
/*reverse list start from head*/
func reverse(head *ListNode) *ListNode {
var prev, curr *ListNode = nil, head
for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}
return prev
}
/*reverse the list between from and to th node*/
func (lst *List) Reverse(from, to int) {
if from < 0 || from >= lst.Len || to < 0 ||
to >= lst.Len || from > to {
panic("index out of boundary")
}
if from == to {
return
}
var start, end, before, next *ListNode
curr := lst.Head
//fint the four point before reverse
for cnt := 0; cnt <= to; cnt++ {
if cnt < from {
before = curr
}
if cnt == from {
start = curr
}
if cnt == to {
end = curr
}
curr = curr.Next
}
next = end.Next
end.Next = nil //break the from-to list
//re-link from-to list head
if before != nil {
before.Next = reverse(start)
} else {
lst.Head = reverse(start)
}
//re-link from-to list to remain part
start.Next = next
lst.Tail = start
//update list tail
for lst.Tail.Next != nil {
lst.Tail = lst.Tail.Next
}
}
最后，添加测试用例来验证程序
func LstTest() {
nums := []Val_t{3, 5, 2, 4, 6}
lst := NewList()
lst.Ints2Lst(nums)
lst.Print()
lst.Reverse(0, lst.Len-1)
lst.Print()
/*lst.PushBack(7)
lst.PushFront(1)
lst.Print()
lst.InsertAt(4, 3)
lst.Print()
fmt.Printf("3rd item: %v\n", lst.GetAt(3))
lst.PopBack()
lst.PopFront()
fmt.Printf("remove 3rd item: %v \n", lst.RemoveAt(3))
lst.Print()*/
}
代码清单：https://github.com/KevinACoder/Learning/blob/master/ds_go/kit/list.go
网友评论