Go36-8,9-鏈表、字典

鏈表

Go語言的鏈表實現在其標準庫的container/list代碼包中。
這個包包含了2個程序實體：

• List : 實現了一個雙向鏈表
• Element : 代表了鏈表中元素的結構

操作鏈表

移動鏈表里的元素：

func (l *List) MoveBefore(e, mark *Element)  // 把元素e移動到mark元素的前面
func (l *List) MoveAfter(e, mark *Element)  // 把元素e移動到mark元素的后面
func (l *List) MoveToFront(e *Element)  // 把元素e移動到鏈表的最前端
func (l *List) MoveToBack(e *Element)  // 把元素e移動到鏈表的最后端

上面的方法都是調整鏈表l里元素的位置，e和mark原本都是鏈表里的元素，執行方法后，只是調整元素e在鏈表中的位置。所以操作前后鏈表里包含的元素并不會有差別，只是e元素的位置可能變化了。

添加元素
鏈表里的元素都是*Element類型。List包中那些用于插入新元素的方法都只接收interface{}類型的值。這個方法內部都會用Element包裝接收到的新元素：

func (l *List) InsertBefore(v interface{}, mark *Element) *Element  // 在mark元素之前插入行元素
func (l *List) InsertAfter(v interface{}, mark *Element) *Element  // 在mark元素之后插入行元素
func (l *List) PushFront(v interface{} *Element) *Element  // 在鏈表的最前端添加新元素
func (l *List) PushBack(v interface{} *Element) *Element  // 在鏈表的最后端添加新元素

上面的方法都會返回一個指針*Element。也就是插入元素的*Element類型。

獲取元素
通過鏈表，可以直接取到鏈表頭尾的元素，這是一個雙向鏈表。然后有了鏈表中的某個元素之后，就可以拿到該元素前一個或后一個元素了：

func (l *List) Front() *Element  // 獲取到鏈表中最前端的元素
func (l *List) Back() *Element  // 獲取到鏈表中最后端的元素
func (e *Element) Next() *Element  // 獲取當前元素的下一個元素
func (e *Element) Prev() *Element  //  獲取當前元素的前一個元素

鏈表的機制

下面是官方文檔里的List類型的描述，隱藏了私有字段：

type List struct {
    // contains filtered or unexported fields
}

List這個結構體類型有兩個字段，一個是Element類型的字段root，代碼鏈表的根元素；另一個是int類型的字段len，代表鏈表的長度。都是包級私有的，我們無法查看和修改它們。

下面是Element類型的描述，同樣的隱藏了私有字段：

type Element struct {

    // The value stored with this element.
    Value interface{}
    // contains filtered or unexported fields
}

Element類型里分別有一個用于存儲前一個元素和后一個元素以及所屬鏈表的指針值。另外還有一個公開字段Value，就是元素的值。

延遲初始化機制
所謂延遲初始化，你可以理解為把初始化操作延后，僅在實際需要的時候才進行。延遲初始化的優點在于“延后”，它可以分散初始化操作帶來的計算量和存儲空間消耗。
然而，延遲初始化的缺點恰恰也在于“延后”。如果在調用鏈表的每個方法的時候，都需要去判斷鏈表是否已經被初始化的話，那么也是一個計算量上的浪費。
在這里的鏈表的實現中，一些方法是無需對是否初始化做判斷的。比如：
Front和Back方法，一旦發現鏈表的長度為0，就可以直接返回nil。
刪除、移動、刪除鏈表元素時，判斷一下傳入元素中的所屬鏈表的指針，是否與當前鏈表的指針相同。相等，就說明這個鏈表已經被初始化了，否則說明元素在不要操作的鏈表中，那么就直接返回。
上面的操作，應該都是要鏈表是已經完成初始化的，但是未初始化過的鏈表，通過上面的機制，也能正確返回。這樣初始化的操作就可以只在必要的時候才進行，比如：
PushFront、PushBack、PushBackList、PushFrontList，這些方法，會先判斷鏈表的動態。如果沒有初始化，就進行初始化。
所以，List利用了自身，以及Element在結構上的特點，平衡了延遲初始化的優缺點。

循環鏈表

在Go標準庫的container/ring包中的Ring類型實現的是一個循環鏈表。

type Ring struct {
    Value interface{} // for use by client; untouched by this library
    // contains filtered or unexported fields
}

其實List在內部就是一個循環鏈表。它的根元素永遠不會持有任何實際的元素值，而該元素的存在，就是為了連接這個循環鏈表的首尾兩端。
所以，List的零值是一個只包含了根元素，但不包含任何實際元素值的空鏈表。

說List在內部就是一個循環鏈表，是它設計的邏輯，這個在最后我去源碼里看了一下。這里并不是指List是通過這里的container/ring包實現的。而是List本身其實也是一個循環鏈表的結構，Ring是Go提供的一個實現循環鏈表的標準庫，Ring本身當然也是一個循環鏈表的結構。

Ring和List在本質上都是循環鏈表，主要有以下的幾點不同：
Ring類型的數據結構僅由它自身即可代表，而List類型則需要由它以及Element類型聯合表示。這是表示方式上的不同，也是結構復雜度上的不同。
Ring類型的值，只代表了其所屬的循環鏈表中的一個元素，而List類型的值則代表了一個完整的鏈表。這是表示維度上的不同。
在創建并初始化一個Ring值的時候，要指定它包含的元素的數量，但是List不能也不需要指定數量。這是兩個代碼包中的New函數在功能上的不同，也是兩個類型在初始化值方面的第一個不同。
通過var r ring.Ring語句聲明的r將會是一個長度為1的循環鏈表，而List類型的零值則是一個長度為0的鏈表。List中的根元素不會持有實際元素值，因此計算長度時不會包含它。這是兩個類型在初始化值方面的第二個不同。
Ring值的Len方法的算法復雜度是O(N)的，而List值的Len方法的算法復雜度則是 O(1)的。這是兩者在性能方面最顯而易見的差別。
關于上的len方法，因為List的結構體里直接就記了表示長度的私有字段len。而Ring不像List那樣有一個表示整個鏈表的結構體。兩個包里的len方法的源碼如下：

// src/container/ring/ring.go
func (r *Ring) Len() int {
    n := 0
    if r != nil {
        n = 1
        for p := r.Next(); p != r; p = p.next {
            n++
        }
    }
    return n
}

// src/container/list/list.go
func (l *List) Len() int { return l.len }

小結

上面先講了鏈表，并且展開了鏈表的一些使用技巧和實現特點。由于鏈表本身內部就是一個循環鏈表。所以又和container/ring包中的循環鏈表做了一番比較。
另外，container一共有3個子包，上面講到了2個，還有一個是container/heap，就是堆。

List的循環結構

關于List內部就是一個循環鏈表的問題，自己又去源碼里探究了一番。
下面是Init方法，把root元素的下一個元素和前一個元素都指向自己，形成了一個環。并且把長度字段len設置成0：

func (l *List) Init() *List {
    l.root.next = &l.root
    l.root.prev = &l.root
    l.len = 0
    return l
}

雖然List本質是個環，但是使用的時候，不是環而是有頭和尾的一條鏈。在獲取下一個元素的時候，如果到了最后端，那么next的下一個元素就是root元素。這時不返回root，而是返回nil。這就是根元素不持有任何元素，只是連接鏈表的首尾兩端：

func (e *Element) Next() *Element {
    if p := e.next; e.list != nil && p != &e.list.root {
        return p
    }
    return nil
}

字典

字典（map）里存儲的是鍵值對。在Go語言了，為了避免歧義，換了一種稱呼，叫“鍵-元素 對”。
Go語言的字典類型其實是一個哈希表（hash table）的特定實現。在這個實現中，鍵和元素的最大不同在于，鍵的類型是受限的，而元素可以是任意的類型。

鍵的類型限制

鍵的類型不可以是函數類型、字典類型和切片類型。
鍵類型的值之間必須可以施加操作符==和!=，就是支持判等操作。上述三種類型的值不支持判等操作。
如果鍵的類型是接口類型，那么鍵值（這里是鍵的值，就是會引起歧義的地方，好在我們已經把原來的值的叫法改成元素了）的實際類型也不能是上述三種類型。

package main

import "fmt"

func main() {
    var badMap = map[interface{}]int{
        "one": 1,
        2: 2,
        [1]int{3}: 3,  // 數組是合法的鍵
        // []int{4}: 4,  // 切片不能作為鍵，加上這句會Panic
    }
    fmt.Println(badMap)
}

像上面這樣，鍵的類型為空接口interface{}，是合法的鍵。但是如果這個空接口實際的值類型是無法作為鍵的類型也是不行的。并且這種情況編譯器無法檢查到。或者說，通過這樣的聲明躲過了編譯器的檢查。最終在運行的時候是會崩潰的（Panic）。
由于會有上面這種可以躲過編譯器檢查的方法，最好不要把字典的key設定為任何借口類型。如果一定要這么做，那么就盡量確保代碼可可控的范圍內。
同樣的道理，如果鍵的類型是數組類型，也要確保數組了的元素的類型不是函數、字典或切片。
結構體類型也可以作為鍵，同樣要確保結構體中的所有的字段都是合法的類型。

字典的初始化

下面的操作只是聲明一個字典，并未做初始化：

var m1 map[string]string

這里要討論一個字典未做初始化的問題。字典是引用類型，所以只做了聲明而沒有初始化的時候，它的值是nil。
在這樣的一個值為nil的字典上，除了添加元素以外，做其他任何操作都不會引起錯誤。比如，可以查找字典里是否有某個鍵、刪除某個鍵、或者獲取長度。
如果要添加元素，就要先對字典做初始化，否則會拋出Panic。