509
如何用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，此時的單鏈表如何實現？這樣實現的代碼在插入刪除操作時候是不是更容易點？
最後更新：2017-11-09 17:33:34