學習筆記-container包中的那些容器

參考：https://time.geekbang.org/column/article/14117

1、那么 Go 語言的鏈表是什么樣的呢？

Go 語言的鏈表實現在標準庫的container/list代碼包中。這個代碼包中有兩個公開的程序實體——List和Element，List 實現了一個雙向鏈表（以下簡稱鏈表），而 Element 則代表了鏈表中元素的結構。

2、可以把自己生成的Element類型值傳給鏈表嗎？

這里用到了List的四種方法。
MoveBefore方法和MoveAfter方法，它們分別用于把給定的元素移動到另一個元素的前面和后面。MoveToFront方法和MoveToBack方法，分別用于把給定的元素移動到鏈表的最前端和最后端。在這些方法中，“給定的元素”都是Element類型的，Element類型是Element類型的指針類型，*Element的值就是元素的指針。

果我們自己生成這樣的值，然后把它作為“給定的元素”傳給鏈表的方法，那么會發生什么？鏈表會接受它嗎？

func (l *List) MoveBefore(e, mark *Element)
func (l *List) MoveAfter(e, mark *Element)

func (l *List) MoveToFront(e *Element)
func (l *List) MoveToBack(e *Element)

答案：不會接受，這些方法將不會對鏈表做出任何改動。因為我們自己生成的Element值并不在鏈表中，所以也就談不上“在鏈表中移動元素”。更何況鏈表不允許我們把自己生成的Element值插入其中。

在List包含的方法中，用于插入新元素的那些方法都只接受interface{}類型的值。這些方法在內部會使用Element值，包裝接收到的新元素。這樣做正是為了避免直接使用我們自己生成的元素，主要原因是避免鏈表的內部關聯，遭到外界破壞，這對于鏈表本身以及我們這些使用者來說都是有益的。

3、List的方法還有下面這幾種：

Front和Back方法分別用于獲取鏈表中最前端和最后端的元素
InsertBefore和InsertAfter方法分別用于在指定的元素之前和之后插入新元素
PushFront和PushBack方法則分別用于在鏈表的最前端和最后端插入新元素。

這些方法都會把一個Element值的指針作為結果返回，它們就是鏈表留給我們的安全“接口”。拿到這些內部元素的指針，我們就可以去調用前面提到的用于移動元素的方法了。

func (l *List) Front() *Element
func (l *List) Back() *Element

func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) InsertAfter(v interface{}, mark *Element) *Element

func (l *List) PushFront(v interface{}) *Element
func (l *List) PushBack(v interface{}) *Element

4、為什么鏈表可以做到開箱即用？

List和Element都是結構體類型。結構體類型有一個特點，那就是它們的零值都會是擁有特定結構，但是沒有任何定制化內容的值，相當于一個空殼。值中的字段也都會被分別賦予各自類型的零值。

廣義來講，所謂的零值就是只做了聲明，但還未做初始化的變量被給予的缺省值。每個類型的零值都會依據該類型的特性而被設定。比如，經過語句var a [2]int聲明的變量a的值，將會是一個包含了兩個0的整數數組。又比如，經過語句var s []int聲明的變量s的值將會是一個[]int類型的、值為nil的切片。

那么經過語句var l list.List聲明的變量l的值將會是什么呢？[1] 這個零值將會是一個長度為0的鏈表。這個鏈表持有的根元素也將會是一個空殼，其中只會包含缺省的內容。那這樣的鏈表我們可以直接拿來使用嗎？

答案是：可以的。這被稱為“開箱即用”。Go 語言標準庫中很多結構體類型的程序實體都做到了開箱即用。這也是在編寫可供別人使用的代碼包（或者說程序庫）時，我們推薦遵循的最佳實踐之一。那么，語句var l list.List聲明的鏈表l可以直接使用，這是怎么做到的呢？

關鍵在于它的“延遲初始化”機制。所謂的延遲初始化，你可以理解為把初始化操作延后，僅在實際需要的時候才進行。延遲初始化的優點在于“延后”，它可以分散初始化操作帶來的計算量和存儲空間消耗。

例如，如果我們需要集中聲明非常多的大容量切片的話，那么那時的 CPU 和內存空間的使用量肯定都會一個激增，并且只有設法讓其中的切片及其底層數組被回收，內存使用量才會有所降低。

如果數組是可以被延遲初始化的，那么計算量和存儲空間的壓力就可以被分散到實際使用它們的時候。這些數組被實際使用的時間越分散，延遲初始化帶來的優勢就會越明顯。

實際上，Go 語言的切片就起到了延遲初始化其底層數組的作用，你可以想一想為什么會這么說的理由。延遲初始化的缺點恰恰也在于“延后”。你可以想象一下，如果我在調用鏈表的每個方法的時候，它們都需要先去判斷鏈表是否已經被初始化，那這也會是一個計算量上的浪費。在這些方法被非常頻繁地調用的情況下，這種浪費的影響就開始顯現了，程序的性能將會降低。

在這里的鏈表實現中，一些方法是無需對是否初始化做判斷的。比如Front方法和Back方法，一旦發現鏈表的長度為0, 直接返回nil就好了。

又比如，在用于刪除元素、移動元素，以及一些用于插入元素的方法中，只要判斷一下傳入的元素中指向所屬鏈表的指針，是否與當前鏈表的指針相等就可以了。

如果不相等，就一定說明傳入的元素不是這個鏈表中的，后續的操作就不用做了。反之，就一定說明這個鏈表已經被初始化了。

原因在于，鏈表的PushFront方法、PushBack方法、PushBackList方法以及PushFrontList方法總會先判斷鏈表的狀態，并在必要時進行初始化，這就是延遲初始化。

而且，我們在向一個空的鏈表中添加新元素的時候，肯定會調用這四個方法中的一個，這時新元素中指向所屬鏈表的指針，一定會被設定為當前鏈表的指針。所以，指針相等是鏈表已經初始化的充分必要條件。

5、Ring與List的區別在哪兒？

container/ring包中的Ring類型實現的是一個循環鏈表，也就是我們俗稱的環。其實List在內部就是一個循環鏈表。它的根元素永遠不會持有任何實際的元素值，而該元素的存在就是為了連接這個循環鏈表的首尾兩端。

所以也可以說，List的零值是一個只包含了根元素，但不包含任何實際元素值的空鏈表。那么，既然Ring和List在本質上都是循環鏈表，那它們到底有什么不同呢？

（1）Ring類型的數據結構僅由它自身即可代表，而List類型則需要由它以及Element類型聯合表示。這是表示方式上的不同，也是結構復雜度上的不同。

（2）一個Ring類型的值嚴格來講，只代表了其所屬的循環鏈表中的一個元素，而一個List類型的值則代表了一個完整的鏈表。這是表示維度上的不同。
（3）在創建并初始化一個Ring值的時候，我們可以指定它包含的元素的數量，但是對于一個List值來說卻不能這樣做（也沒有必要這樣做）。循環鏈表一旦被創建，其長度是不可變的。這是兩個代碼包中的New函數在功能上的不同，也是兩個類型在初始化值方面的第一個不同。
（4）僅通過var r ring.Ring語句聲明的r將會是一個長度為1的循環鏈表，而List類型的零值則是一個長度為0的鏈表。別忘了List中的根元素不會持有實際元素值，因此計算長度時不會包含它。這是兩個類型在初始化值方面的第二個不同。
（5）Ring值的Len方法的算法復雜度是 O(N) 的，而List值的Len方法的算法復雜度則是 O(1) 的。這是兩者在性能方面最顯而易見的差別。
其他的不同基本上都是方法方面的了。比如，循環鏈表也有用于插入、移動或刪除元素的方法，不過用起來都顯得更抽象一些，等等。

擴展知識點：

[1]：List這個結構體類型有兩個字段，一個是Element類型的字段root，另一個是int類型的字段len。顧名思義，前者代表的就是那個根元素，而后者用于存儲鏈表的長度。注意，它們都是包級私有的，也就是說使用者無法查看和修改它們。

像前面那樣聲明的l，其字段root和len都會被賦予相應的零值。len的零值是0，正好可以表明該鏈表還未包含任何元素。由于root是Element類型的，所以它的零值就是該類型的空殼，用字面量表示的話就是Element{}。

Element類型包含了幾個包級私有的字段，分別用于存儲前一個元素、后一個元素以及所屬鏈表的指針值。另外還有一個名叫Value的公開的字段，該字段的作用就是持有元素的實際值，它是interface{}類型的。在Element類型的零值中，這些字段的值都會是nil。