Go語言核心36講(Go語言進階技術二)--學習筆記

語言: CN / TW / HK

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 國際許可協議 進行許可。

歡迎轉載、使用、重新發布,但務必保留文章署名 鄭子銘 (包含連結: http://www.cnblogs.com/MingsonZheng/ ),不得用於商業目的,基於本文修改後的作品務必以相同的許可釋出。