Go語言核心36講（Go語言進階技術二）–學習筆記

08 | container包中的那些容器

我們在上次討論了數組和切片，當我們提到數組的時候，往往會想起鏈表。那麼 Go 語言的鏈表是什麼樣的呢？

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

那麼，我今天的問題是：可以把自己生成的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值，包裝接收到的新元素。

這樣做正是為了避免直接使用我們自己生成的元素，主要原因是避免鏈表的內部關聯，遭到外界破壞，這對於鏈表本身以及我們這些使用者來說都是有益的。

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

Front和Back方法分別用於獲取鏈表中最前端和最後端的元素，

InsertBefore和InsertAfter方法分別用於在指定的元素之前和之後插入新元素，PushFront和PushBack方法則分別用於在鏈表的最前端和最後端插入新元素。

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

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

知識擴展

1. 問題：為什麼鏈表可以做到開箱即用？

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

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

那麼經過語句var l list.List聲明的變數l的值將會是什麼呢？

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

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

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

這個零值將會是一個長度為0的鏈表。這個鏈表持有的根元素也將會是一個空殼，其中只會包含預設的內容。那這樣的鏈表我們可以直接拿來使用嗎？

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

關鍵在於它的「延遲初始化」機制。

所謂的延遲初始化，你可以理解為把初始化操作延後，僅在實際需要的時候才進行。延遲初始化的優點在於「延後」，它可以分散初始化操作帶來的計算量和存儲空間消耗。

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

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

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

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

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

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

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

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

明白了嗎？List利用了自身以及Element在結構上的特點，巧妙地平衡了延遲初始化的優缺點，使得鏈表可以開箱即用，並且在性能上可以達到最優。

問題 2：Ring與List的區別在哪兒？

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

所以也可以說，List的零值是一個只包含了根元素，但不包含任何實際元素值的空鏈表。那麼，既然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) 的。這是兩者在性能方面最顯而易見的差別。

其他的不同基本上都是方法方面的了。比如，循環鏈表也有用於插入、移動或刪除元素的方法，不過用起來都顯得更抽象一些，等等。

總結

我們今天主要討論了container/list包中的鏈表實現。我們詳細講解了鏈表的一些主要的使用技巧和實現特點。由於此鏈表實現在內部就是一個循環鏈表，所以我們還把它與container/ring包中的循環鏈表實現做了一番比較，包括結構、初始化以及性能方面。

思考題

  • container/ring包中的循環鏈表的適用場景都有哪些？
  • 你使用過container/heap包中的堆嗎？它的適用場景又有哪些呢？

參考閱讀

切片與數組的比較

切片本身有著佔用記憶體少和創建便捷等特點，但它的本質上還是數組。切片的一大好處是可以讓我們通過窗口快速地定位並獲取，或者修改底層數組中的元素。

不過，當我們想刪除切片中的元素的時候就沒那麼簡單了。元素複製一般是免不了的，就算只刪除一個元素，有時也會造成大量元素的移動。這時還要注意空出的元素槽位的「清空」，否則很可能會造成記憶體泄漏。

另一方面，在切片被頻繁「擴容」的情況下，新的底層數組會不斷產生，這時記憶體分配的量以及元素複製的次數可能就很可觀了，這肯定會對程式的性能產生負面的影響。

尤其是當我們沒有一個合理、有效的」縮容「策略的時候，舊的底層數組無法被回收，新的底層數組中也會有大量無用的元素槽位。過度的記憶體浪費不但會降低程式的性能，還可能會使記憶體溢出並導致程式崩潰。

由此可見，正確地使用切片是多麼的重要。不過，一個更重要的事實是，任何數據結構都不是銀彈。不是嗎？數組的自身特點和適用場景都非常鮮明，切片也是一樣。它們都是 Go 語言原生的數據結構，使用起來也都很方便. 不過，你的集合類工具箱中不應該只有它們。這就是我們使用鏈表的原因。

不過，對比來看，一個鏈表所佔用的記憶體空間，往往要比包含相同元素的數組所佔記憶體大得多。這是由於鏈表的元素並不是連續存儲的，所以相鄰的元素之間需要互相保存對方的指針。不但如此，每個元素還要存有它所屬鏈表的指針。

有了這些關聯，鏈表的結構反倒更簡單了。它只持有頭部元素（或稱為根元素）基本上就可以了。當然了，為了防止不必要的遍歷和計算，鏈表的長度記錄在內也是必須的。

知識共享許可協議

本作品採用知識共享署名-非商業性使用-相同方式共享 4.0 國際許可協議進行許可。

歡迎轉載、使用、重新發布，但務必保留文章署名 鄭子銘 （包含鏈接： //www.cnblogs.com/MingsonZheng/ ），不得用於商業目的，基於本文修改後的作品務必以相同的許可發布。

Tags:

VirMach 便宜 VPS

QNews

QNews