Go36-8,9-鏈表、字典

鏈表

Go語(yǔ)言的鏈表實(shí)現(xiàn)在其標(biāo)準(zhǔn)庫(kù)的container/list代碼包中。
這個(gè)包包含了2個(gè)程序?qū)嶓w：

• List : 實(shí)現(xiàn)了一個(gè)雙向鏈表
• Element : 代表了鏈表中元素的結(jié)構(gòu)

操作鏈表

移動(dòng)鏈表里的元素：

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

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

添加元素
鏈表里的元素都是*Element類型。List包中那些用于插入新元素的方法都只接收interface{}類型的值。這個(gè)方法內(nèi)部都會(huì)用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  // 在鏈表的最后端添加新元素

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

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

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

鏈表的機(jī)制

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

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

List這個(gè)結(jié)構(gòu)體類型有兩個(gè)字段，一個(gè)是Element類型的字段root，代碼鏈表的根元素；另一個(gè)是int類型的字段len，代表鏈表的長(zhǎng)度。都是包級(jí)私有的，我們無(wú)法查看和修改它們。

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

type Element struct {

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

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

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

循環(huán)鏈表

在Go標(biāo)準(zhǔn)庫(kù)的container/ring包中的Ring類型實(shí)現(xiàn)的是一個(gè)循環(huán)鏈表。

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

其實(shí)List在內(nèi)部就是一個(gè)循環(huán)鏈表。它的根元素永遠(yuǎn)不會(huì)持有任何實(shí)際的元素值，而該元素的存在，就是為了連接這個(gè)循環(huán)鏈表的首尾兩端。
所以，List的零值是一個(gè)只包含了根元素，但不包含任何實(shí)際元素值的空鏈表。

說(shuō)List在內(nèi)部就是一個(gè)循環(huán)鏈表，是它設(shè)計(jì)的邏輯，這個(gè)在最后我去源碼里看了一下。這里并不是指List是通過(guò)這里的container/ring包實(shí)現(xiàn)的。而是List本身其實(shí)也是一個(gè)循環(huán)鏈表的結(jié)構(gòu)，Ring是Go提供的一個(gè)實(shí)現(xiàn)循環(huán)鏈表的標(biāo)準(zhǔn)庫(kù)，Ring本身當(dāng)然也是一個(gè)循環(huán)鏈表的結(jié)構(gòu)。

Ring和List在本質(zhì)上都是循環(huán)鏈表，主要有以下的幾點(diǎn)不同：
Ring類型的數(shù)據(jù)結(jié)構(gòu)僅由它自身即可代表，而List類型則需要由它以及Element類型聯(lián)合表示。這是表示方式上的不同，也是結(jié)構(gòu)復(fù)雜度上的不同。
Ring類型的值，只代表了其所屬的循環(huán)鏈表中的一個(gè)元素，而List類型的值則代表了一個(gè)完整的鏈表。這是表示維度上的不同。
在創(chuàng)建并初始化一個(gè)Ring值的時(shí)候，要指定它包含的元素的數(shù)量，但是List不能也不需要指定數(shù)量。這是兩個(gè)代碼包中的New函數(shù)在功能上的不同，也是兩個(gè)類型在初始化值方面的第一個(gè)不同。
通過(guò)var r ring.Ring語(yǔ)句聲明的r將會(huì)是一個(gè)長(zhǎng)度為1的循環(huán)鏈表，而List類型的零值則是一個(gè)長(zhǎng)度為0的鏈表。List中的根元素不會(huì)持有實(shí)際元素值，因此計(jì)算長(zhǎng)度時(shí)不會(huì)包含它。這是兩個(gè)類型在初始化值方面的第二個(gè)不同。
Ring值的Len方法的算法復(fù)雜度是O(N)的，而List值的Len方法的算法復(fù)雜度則是 O(1)的。這是兩者在性能方面最顯而易見(jiàn)的差別。
關(guān)于上的len方法，因?yàn)長(zhǎng)ist的結(jié)構(gòu)體里直接就記了表示長(zhǎng)度的私有字段len。而Ring不像List那樣有一個(gè)表示整個(gè)鏈表的結(jié)構(gòu)體。兩個(gè)包里的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 }

小結(jié)

上面先講了鏈表，并且展開(kāi)了鏈表的一些使用技巧和實(shí)現(xiàn)特點(diǎn)。由于鏈表本身內(nèi)部就是一個(gè)循環(huán)鏈表。所以又和container/ring包中的循環(huán)鏈表做了一番比較。
另外，container一共有3個(gè)子包，上面講到了2個(gè)，還有一個(gè)是container/heap，就是堆。

List的循環(huán)結(jié)構(gòu)

關(guān)于List內(nèi)部就是一個(gè)循環(huán)鏈表的問(wèn)題，自己又去源碼里探究了一番。
下面是Init方法，把root元素的下一個(gè)元素和前一個(gè)元素都指向自己，形成了一個(gè)環(huán)。并且把長(zhǎng)度字段len設(shè)置成0：

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

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

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

字典

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

鍵的類型限制

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

package main

import "fmt"

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

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

字典的初始化

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

var m1 map[string]string

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