這天小櫻又做夢了，可惜不是春夢，她春夢都早上做。總之，今天全班要一起去溜冰啦，你們一定會說怎麼又校外教學，沒辦法小櫻那間是貴族學校啊~ 但是每次校外教學或特別活動，一定都會出事，跟小櫻同班真倒楣，沒事還要被冰住(啊！不小心把劇情講出來了)

小櫻正在努力與Golang牌博鬥，螢幕前的魔法使們，也該動動手指一起來努力練功了吧！

想必經歷前20堂課程的魔法使們，應該都對Golang的語法很熟悉了，所以接下來會把課程代入(手刻)資料結構的部份

什麼是 linked list 鏈結串列？

Linked list 是指將一塊資料透過指標連結到下一個資料。

圖源：連結串列 - 維基百科，自由的百科全書

可以把 Linked list 當成一個新的型態，但是這個型態必需支援以下幾種操作：

type Node struct{
    Val   interface{}
    Next *Node
}

type LinkedList interface{
    Prepend(*Node)    // 將節點插入串列開頭
    Append(*Node)     // 將節點插入串列結尾
    Pop() *Node       // 將節點自尾部移除並返回節點
    PopFirst() *Node  // 將節點自頭部移除並返回節點
    Head() *Node      // 取點頭節點
    Tail()            // 取得尾節點
    Remove(*Node)     // 移除指定節點
}

那麼就開始我們的(手刻)旅程吧！

創建package

首先我們先創建一個 package，至於要怎麼創建？請複習：#14 套件 Package (2020) & 套件實戰(math, http, sort) | Golang魔法使

因為 linked-list 太長了，就簡稱 ll 吧！

我們先建立一些基本的結構體：

./ll/linkedlist.go

package ll
import "fmt"

type Node struct{
    Val interface{}
    Next *Node
}

type LinkedList struct{
    head *Node    // 指向開始的 Node
    tail *Node    // 指向結束的 Node
}

func New() *LinkedList{
    return new(LinkedList)
}

func NewNode(val interface{}) *Node{
    n := new(Node)
    n.Val = val
    return n
}

實作 Prepend(), Append() 為了維持運作，特別又創了一個私有(private)方法(僅有 ll 包內可調用)

func (l *LinkedList) isEmpty() bool{
    return l.head == nil
}

func (l *LinkedList) Prepend(n *Node){
    if l.isEmpty(){
        l.head = n
        l.tail = n
        return
    }
    n.Next = l.head     // 將新節點的下個點指向原串列的頭
    l.head = n          // 將開頭改成新節點
}

func (l *LinkedList) Append(n *Node){
    if l.isEmpty(){
        l.head = n
        l.tail = n
        return
    }
    l.tail.Next = n     // 將結尾的下個點指向新節點
    l.tail = n          // 將結尾改成新節點
}

實作 Pop(), PopFirst()，其中因為我們不知道倒數第二個結點所以 Pop()在 實作上麻煩一些

func (l *LinkedList) Pop() (*Node, error){
    // 串列為空 (噴錯)
    if l.isEmpty(){
        return nil, fmt.Errorf("Linked-List is empty")
    }

    var previous *Node
    // 串列只有一個值
    if l.head == l.tail{
        previous = l.head
        l.head = nil    // 恢復成預設值
        l.tail = nil    // 恢復成預設值
        return previous, nil
    }

    for current := l.head; current != l.tail; current = current.Next{
        previous = current
    }

    // previous 為倒數第二個節點
    tmp := previous.Next
    previous.Next = nil
    l.tail = previous
    return tmp, nil
}

func (l *LinkedList) PopFirst() (*Node, error){
    // 串列為空 (噴錯)
    if l.isEmpty(){
        return nil, fmt.Errorf("Linked-List is empty")
    }
    // 串列只有一個值
    if l.head == l.tail{
        l.tail = nil     // 恢復成預設值
    }

    tmp := l.head
    l.head = l.head.Next // 將開頭指向第二個節點
    return tmp, nil
}

實作 Head() 回傳頭結點、及 Tail() 回傳尾結點

func (l *LinkedList) Head() *Node{
    return l.head
}

func (l *LinkedList) Tail() *Node{
    return l.tail
}

實作 Remove() ，這個也滿麻煩的，主要是要從頭開始找，找到欲移除的節點的前一個節點，將其指向欲移除的節點的下一個節點。如果欲移除頭節點，會很麻煩，因為頭結點的前一個點沒有東西，所以改交由 PopFirst() 處理

func (l *LinkedList) Remove(n *Node) error{
    // 欲移除之節點為頭節點
    if n == l.head{
        _, err := l.PopFirst()
        return err
    }

    var previous *Node
    current := l.head
    for ; current != n && current != nil; current = current.Next{
        previous = current
    }

    // 代表 n 不在串列中
    if current == nil{
        return fmt.Errorf("%v is not in the linked list", n)
    }

    // previous 是節點 n 前的一個點
    previous.Next = previous.Next.Next
    return nil
}

實際調用

本教學採用新的套件模式 (go version >= 1.11)，預設 module 名稱為 practice ，所以要 import "practice/ll"

• ./
  • go.mod (利用 go mod init 建立)
  • ll/
    • linkedlist.go (剛剛創建的包)
  • lesson21.go (準備調用)

./lesson21.go

package main
import(
    "fmt"
    "practice/ll"
)

func print(l *ll.LinkedList){
    for current := l.Head(); current != nil; current = current.Next{
        fmt.Printf("%v -> ", current.Val)
    }
    fmt.Println("nil")
}

func main(){
    myLikedList := ll.New()
    print(myLikedList)      // nil

    myLikedList.Append(ll.NewNode("小櫻"))
    print(myLikedList)      // 小櫻 -> nil

    myLikedList.Append(ll.NewNode("小狼"))
    print(myLikedList)      // 小櫻 -> 小狼 -> nil
    myLikedList.Prepend(ll.NewNode("知世"))
    print(myLikedList)      // 知世 -> 小櫻 -> 小狼 -> nil

    node, err := myLikedList.Pop()
    if err != nil{
        fmt.Println(err)
    }else{
        fmt.Println("Pop()", node.Val)      // Pop() 小狼
    }
    print(myLikedList)      // 知世 -> 小櫻 -> nil

    node, err = myLikedList.PopFirst()
    if err != nil{
        fmt.Println(err)
    }else{
        fmt.Println("PopFirst()", node.Val) // PopFirst() 知世
    }
    print(myLikedList)      // 小櫻 -> nil

    node, err = myLikedList.Pop()
    if err != nil{
        fmt.Println(err)
    }else{
        fmt.Println("Pop()", node.Val)      // Pop() 小櫻
    }
    print(myLikedList)      // nil

    // 故意再取一個
    node, err = myLikedList.Pop()
    if err != nil{
        fmt.Println(err)    // Linked-List is empty
    }else{
        fmt.Println("Pop()", node.Val)
    }

    myLikedList.Append(ll.NewNode("小可"))
    myLikedList.Append(ll.NewNode("莓玲"))
    touya := ll.NewNode("桃矢")
    myLikedList.Append(touya)
    myLikedList.Append(ll.NewNode("雪兔"))
    print(myLikedList)      // 小可 -> 莓玲 -> 桃矢 -> 雪兔 -> nil

    myLikedList.Remove(touya)
    print(myLikedList)      // 小可 -> 莓玲 -> 雪兔 -> nil

    fmt.Println("Head()", myLikedList.Head().Val)   // Head() 小可
    fmt.Println("Tail()", myLikedList.Tail().Val)   // Tail() 雪兔

    // 故意再移除一次
    err = myLikedList.Remove(touya)
    if err != nil{
        fmt.Println(err)    // &{桃矢 0xc00005c500} is not in the linked list
    }
}

Golang 本身提供的 list

Golang 本身也有提供 list 的 package，是用雙向的鏈結串列(doubly linked list)實作

list - The Go Programming Language

如果很閒的朋友也可以試試看刻一個雙向鏈結串列出來，簡單來說就是一個節點除了往後一個指，也有往前一個指。

本文圖片來自：

• 庫洛魔法使第一季第卅三集