Golang原始碼 container 系列二 list連結串列
關於ring,可以參考Golang原始碼 container 系列一 ring環形連結串列 ,list也是個連結串列,但是稍有差別。
參考【Go】筆記五 | container包中的list與ring
一、原始碼對比
type Ring struct { next, prev *Ring Valueinterface{} } // Element is an element of a linked list. type Element struct { // Next and previous pointers in the doubly-linked list of elements. // To simplify the implementation, internally a list l is implemented // as a ring, such that &l.root is both the next element of the last // list element (l.Back()) and the previous element of the first list // element (l.Front()). next, prev *Element // The list to which this element belongs. list *List // The value stored with this element. Value interface{} } // New creates a ring of n elements. func New(n int) *Ring { if n <= 0 { return nil } r := new(Ring) p := r for i := 1; i < n; i++ { p.next = &Ring{prev: p} p = p.next } p.next = r r.prev = p return r } // List represents a doubly linked list. // The zero value for List is an empty list ready to use. type List struct { root Element // sentinel list element, only &root, root.prev, and root.next are used lenint// current list length excluding (this) sentinel element } // Init initializes or clears list l. func (l *List) Init() *List { l.root.next = &l.root l.root.prev = &l.root l.len = 0 return l } // New returns an initialized list. func New() *List { return new(List).Init() }
二、區別
1.經過語句var l list.List宣告的變數l的值將會是怎樣的?
這個零值將會是一個長度為0的連結串列。這個連結串列持有的根元素也將會是一個空殼,其中只會包含預設的內容。
2.那這樣的連結串列我們可以直接拿來使用嗎?
可以的。這被稱為“開箱即用”。Go 語言標準庫中的很多結構體,都做到了開箱即用。這也是在編寫可供別人使用的程式碼包(或者說.程式庫)時我們推薦遵循的最佳實踐之一。
3.可以把自己生成的Element型別值傳給連結串列嗎?
不會接受,這些方法將不會對連結串列做出任何改動。因為我們自己生成的值並不在連結串列中,所以也就談不上“在連結串列中移動元素”。更何況連結串列不允許我們把自己生成的值插入其中。
4.為什麼不接受自己生成的Element型別值?
在List包含的方法中,用於插入新元素的那些方法都只接受interface{}型別的值。這些方法在內部會使用Element值包裝接收到的新元素。這樣做正是為了避免直接使用我們自己生成的元素,主要原因是避免連結串列的內部關聯遭到外界破壞,這對於連結串列本身以及我們這些使用者來說,都是有益的。
//InsertBefore和InsertAfter分別用於在指定的元素之前和之後插入資料. //PushFront和PushBack則是向連結串列最前端和最後端插入資料. 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
5.Ring與List的區別在哪兒?
container/ring包中的Ring型別實現的是一個迴圈連結串列,也就是我們俗稱的環。其實List在內部就是一個迴圈連結串列。它的根元素永遠不會持有任何實際的元素值,而該元素的存在,就是為了連線這個迴圈連結串列的首尾兩端。
所以也可以說,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)的。這是兩者在效能方面最顯而易見的差別。