深入了解Golang官方container/list原理

更新時(shí)間：2023年08月03日 15:19:40 作者：ag9920

在?Golang?的標(biāo)準(zhǔn)庫(kù)?container?中，包含了幾種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，其實(shí)是非常好的學(xué)習(xí)材料，本文主要為大家介紹了container/list的原理與使用，感興趣的可以了解一下

開(kāi)篇

我們繼續(xù)上一篇解析 Golang 官方 container/heap 用法學(xué)習(xí) Golang 的標(biāo)準(zhǔn)庫(kù) container 中，包含的常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，今天的主角是 container/list。

container/list 封裝了雙向鏈表的實(shí)現(xiàn)，其實(shí)在面試中我們經(jīng)常被問(wèn)到如何實(shí)現(xiàn)一個(gè)雙向鏈表，雖然并不難，但總會(huì)有邊邊角角的處理需要小心。今天，我們就來(lái)結(jié)合源碼，思考一下官方的同學(xué)是怎么基于 Golang 設(shè)計(jì)出一個(gè)雙向鏈表的實(shí)現(xiàn)。

container/list

list 是 Golang 一經(jīng)推出就提供的能力，除了在 1.2 版本添加了 MoveAfter, MoveBefore 后，到目前為止就沒(méi)有別的迭代了。這一套實(shí)現(xiàn)是穩(wěn)定可靠的，而且源碼不過(guò) 240 行，沒(méi)有外部依賴(lài)，非常適合初學(xué)者練手。

我們來(lái)看看官方提供的使用示例：

import (
	"container/list"
	"fmt"
)
func main() {
	// Create a new list and put some numbers in it.
	l := list.New()
	e4 := l.PushBack(4)
	e1 := l.PushFront(1)
	l.InsertBefore(3, e4)
	l.InsertAfter(2, e1)
	// Iterate through list and print its contents.
	for e := l.Front(); e != nil; e = e.Next() {
		fmt.Println(e.Value)
	}
}

首先使用 list.New() 方法創(chuàng)建一個(gè) List 對(duì)象，隨后就可以按照鏈表的正常邏輯去添加，刪除，移動(dòng) Element。最后不斷從 l.Front() 拿到數(shù)據(jù)，并通過(guò) Next() 迭代，就可以遍歷鏈表，輸出的結(jié)果如下：

1
2
3
4

整體來(lái)看，container/list 包封裝了兩個(gè)結(jié)構(gòu)：

List: 一個(gè)雙向鏈表
Element: 一個(gè)鏈表中的元素

提供的能力也可以滿足大部分場(chǎng)景的需要：

下面我們來(lái)結(jié)合源碼看看 Element 和 List 是怎么實(shí)現(xiàn)的。

Element

// 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 any
}

Element 的定義很簡(jiǎn)單，包含了 4 個(gè)部分：

指向前一個(gè)元素的指針；
指向后一個(gè)元素的指針；
當(dāng)前元素所屬的 List；
存儲(chǔ)在當(dāng)前元素的值。

// Next returns the next list element or nil.
func (e *Element) Next() *Element {
	if p := e.next; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}
// Prev returns the previous list element or nil.
func (e *Element) Prev() *Element {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}

作為雙向鏈表的節(jié)點(diǎn)，自然是需要有能力獲取到前一個(gè)元素，以及后一個(gè)元素。不過(guò)注意，這里并不是直接 return e.next 或者 return e.prev。

參考 Element 注釋我們知道：

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

container/list 中的 List 本質(zhì)是個(gè)環(huán)形結(jié)構(gòu)（ring），包含的 root 節(jié)點(diǎn)，既是雙向鏈表中最后一個(gè)元素的 next，也是第一個(gè)元素的 prev。

這個(gè)其實(shí)算法中很常見(jiàn)，本質(zhì)是個(gè) sentinel node，或者叫【哨兵節(jié)點(diǎn)】，從 List 使用者的視角看是感知不到這個(gè) root 存在的。多這一個(gè)節(jié)點(diǎn)，可以有效的幫助我們，操作頭結(jié)點(diǎn)和尾結(jié)點(diǎn)：

虛線框里的東西是真正存儲(chǔ)數(shù)據(jù)的【節(jié)點(diǎn)】，root 不存放數(shù)據(jù)，只用于輔助我們實(shí)現(xiàn)這個(gè)雙向鏈表。

所以，這兒就很好理解了，當(dāng)我們實(shí)現(xiàn) Next() 方法時(shí)需要校驗(yàn)，如果某個(gè)節(jié)點(diǎn)的 next 是 root，說(shuō)明它就是最后一個(gè)了，所以應(yīng)該返回 nil（使用者是感知不到 root 的），Prev() 方法也是同理。

List

// 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
	len  int     // 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() }
// Len returns the number of elements of list l.
// The complexity is O(1).
func (l *List) Len() int { return l.len }

有了前面 root 的推理，這里看 List 就容易多了，和預(yù)期一樣，一個(gè)雙向鏈表對(duì)外只需提供一個(gè)節(jié)點(diǎn)即可，使用者可以調(diào)用 List 的 API 接口進(jìn)行插入，刪除，調(diào)整順序，獲取元素。

這里 List 結(jié)構(gòu)只包含一個(gè) root 元素，并且維護(hù)了一個(gè) len 變量，記錄當(dāng)前鏈表的長(zhǎng)度。我們通過(guò) New() 構(gòu)建出的 List 對(duì)象，只包含 root 一個(gè)元素，所以它的 next 和 prev 都是自己。

獲取頭尾結(jié)點(diǎn)

// Front returns the first element of list l or nil if the list is empty.
func (l *List) Front() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.next
}
// Back returns the last element of list l or nil if the list is empty.
func (l *List) Back() *Element {
	if l.len == 0 {
		return nil
	}
	return l.root.prev
}

Front 和 Back 兩個(gè)方法支持我們獲取鏈表的【頭結(jié)點(diǎn)】和【尾結(jié)點(diǎn)】，有了 root 節(jié)點(diǎn)的輔助，這一點(diǎn)也很容易。root 的下一個(gè)節(jié)點(diǎn)就是頭，root 的前一個(gè)節(jié)點(diǎn)就是尾，看一下我們上面畫(huà)的圖大家就很容易理解了。

基礎(chǔ)鏈表操作

這里我們來(lái)看幾個(gè)底層的鏈表操作，這幾個(gè)方法會(huì)支撐起來(lái) container/list 對(duì)外的 API 實(shí)現(xiàn)：

insert

// insert inserts e after at, increments l.len, and returns e.
func (l *List) insert(e, at *Element) *Element {
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
	e.list = l
	l.len++
	return e
}
// insertValue is a convenience wrapper for insert(&Element{Value: v}, at).
func (l *List) insertValue(v any, at *Element) *Element {
	return l.insert(&Element{Value: v}, at)
}

insert 方法接收 e, at 兩個(gè) Element 指針入?yún)?，它的語(yǔ)義是將 e 元素掛在 at 元素之后。這里的步驟拆解一下：

調(diào)整 e 的前驅(qū)和后繼：

讓 e 的 prev 是 at；
讓 e 的 next 是 at 的 next。

調(diào)整 at 和 at 的 next 的指針，讓 e 作為中間節(jié)點(diǎn)：

讓 e 的 prev（也就是 at）的 next 指向 e；
讓 e 的 next（也就是原來(lái) at 的 next）的 prev 指向 e。

將當(dāng)前的 List 賦值給 e 的 list，調(diào)整長(zhǎng)度即可。

官方還提供了一個(gè) insertValue 作為一個(gè)簡(jiǎn)單的裝飾器，這樣可以直接傳入新節(jié)點(diǎn)的值即可，構(gòu)造節(jié)點(diǎn)這一步在這個(gè)方法內(nèi)發(fā)生。

remove

// remove removes e from its list, decrements l.len
func (l *List) remove(e *Element) {
	e.prev.next = e.next
	e.next.prev = e.prev
	e.next = nil // avoid memory leaks
	e.prev = nil // avoid memory leaks
	e.list = nil
	l.len--
}

刪除節(jié)點(diǎn)很簡(jiǎn)單，其實(shí)就是上面 insert 的逆向操作，找到要?jiǎng)h除的節(jié)點(diǎn) e 的前驅(qū)和后繼，讓它的 prev 的 next 跳過(guò)它，指向更下一個(gè)節(jié)點(diǎn)，讓它的 next 的 prev 也跳過(guò)它，指向更前一個(gè)節(jié)點(diǎn)即可。最后把 len 更新一下。

需要注意的是，很多同學(xué)會(huì)犯錯(cuò)誤，覺(jué)得調(diào)整完前驅(qū)后繼指針即可，但其實(shí)，按照 GC 語(yǔ)言的特性，雖然邏輯上這個(gè)雙向鏈表已經(jīng)沒(méi)有 e 了，但你沒(méi)有把 e 的 next 和 prev 指針清空，就會(huì)導(dǎo)致隨后它們指向的元素有可能不會(huì)被垃圾回收，導(dǎo)致出現(xiàn)內(nèi)存泄漏。

而內(nèi)存泄露的問(wèn)題在線上是很難快速排查的，所以官方也是增加了 e.next = nil 和 e.prev = nil 這樣保證 GC 掃描的時(shí)候不會(huì)漏掉。

move

// move moves e to next to at.
func (l *List) move(e, at *Element) {
	if e == at {
		return
	}
	e.prev.next = e.next
	e.next.prev = e.prev
	e.prev = at
	e.next = at.next
	e.prev.next = e
	e.next.prev = e
}

move 和 insert 比較像，它的語(yǔ)義多一層，代表將 e 從原來(lái)位置挪走，放到 at 的后面。而 insert 是原先 e 不存在于這個(gè)鏈表，新加進(jìn)來(lái)的。

所以，你會(huì)發(fā)現(xiàn)這里多了一步處理：

e.prev.next = e.next
e.next.prev = e.prev

這兩行就是為了處理 e 原來(lái)所在位置的前驅(qū)和后繼，讓它們跳過(guò) e，指向更前或更后的節(jié)點(diǎn)。

后面的 e 和 at 指針的調(diào)整和 insert 是完全對(duì)齊的，大家可以看一下。這里因?yàn)槭?move，不是新增節(jié)點(diǎn)，所以也無(wú)需調(diào)整 len。

API 實(shí)現(xiàn)

有了上面三個(gè)基礎(chǔ)能力：insert, remove, move。配合上 List 的 root 節(jié)點(diǎn)，我們就可以隨心所欲在雙向鏈表里進(jìn)行操作了。這里封裝的對(duì)外 API 很多，但都是基于上面我們提到的能力。

此處我們就不一一贅述了，大家感受一下即可：

// Remove removes e from l if e is an element of list l.
// It returns the element value e.Value.
// The element must not be nil.
func (l *List) Remove(e *Element) any {
	if e.list == l {
		// if e.list == l, l must have been initialized when e was inserted
		// in l or l == nil (e is a zero Element) and l.remove will crash
		l.remove(e)
	}
	return e.Value
}
// PushFront inserts a new element e with value v at the front of list l and returns e.
func (l *List) PushFront(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, &l.root)
}
// PushBack inserts a new element e with value v at the back of list l and returns e.
func (l *List) PushBack(v any) *Element {
	l.lazyInit()
	return l.insertValue(v, l.root.prev)
}
// InsertBefore inserts a new element e with value v immediately before mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertBefore(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark.prev)
}
// InsertAfter inserts a new element e with value v immediately after mark and returns e.
// If mark is not an element of l, the list is not modified.
// The mark must not be nil.
func (l *List) InsertAfter(v any, mark *Element) *Element {
	if mark.list != l {
		return nil
	}
	// see comment in List.Remove about initialization of l
	return l.insertValue(v, mark)
}
// MoveToFront moves element e to the front of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToFront(e *Element) {
	if e.list != l || l.root.next == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, &l.root)
}
// MoveToBack moves element e to the back of list l.
// If e is not an element of l, the list is not modified.
// The element must not be nil.
func (l *List) MoveToBack(e *Element) {
	if e.list != l || l.root.prev == e {
		return
	}
	// see comment in List.Remove about initialization of l
	l.move(e, l.root.prev)
}
// MoveBefore moves element e to its new position before mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveBefore(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark.prev)
}
// MoveAfter moves element e to its new position after mark.
// If e or mark is not an element of l, or e == mark, the list is not modified.
// The element and mark must not be nil.
func (l *List) MoveAfter(e, mark *Element) {
	if e.list != l || e == mark || mark.list != l {
		return
	}
	l.move(e, mark)
}
// PushBackList inserts a copy of another list at the back of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushBackList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Front(); i > 0; i, e = i-1, e.Next() {
		l.insertValue(e.Value, l.root.prev)
	}
}
// PushFrontList inserts a copy of another list at the front of list l.
// The lists l and other may be the same. They must not be nil.
func (l *List) PushFrontList(other *List) {
	l.lazyInit()
	for i, e := other.Len(), other.Back(); i > 0; i, e = i-1, e.Prev() {
		l.insertValue(e.Value, &l.root)
	}
}

比如我們有的時(shí)候需要插入元素，但希望放到某個(gè)節(jié)點(diǎn)之前，這個(gè)時(shí)候類(lèi)似 InsertBefore 的處理，直接拿到目標(biāo)節(jié)點(diǎn)的 prev，插到它的 prev 之后，本質(zhì)上不就是放到了它之前了么？

l.insertValue(v, mark.prev)

這里的代碼都不復(fù)雜，建議大家有需要的時(shí)候?qū)φ諏?shí)現(xiàn)簡(jiǎn)單了解即可。

完整示例

有了上面的源碼解析，我們來(lái)看看怎樣實(shí)用，這里我們附上了鏈表的狀態(tài)。從使用者的角度無(wú)需關(guān)心 root，其實(shí)還是很簡(jiǎn)單基礎(chǔ)的鏈表能力，大家可以嘗試閱讀理解一下下面的調(diào)用結(jié)果：

package main
import (
    "container/list"
    "fmt"
)
func main() {
    l := list.New()
    l.PushBack("a")
    printList(l) // a
    l.PushBack("b")
    printList(l) // a b
    l.PushFront("c")
    printList(l) // c a b
    fmt.Println(l.Front().Value) // c
    fmt.Println(l.Back().Value)  // b
    fmt.Println(l.Len())         // 3
    l.MoveToBack(l.Front())
    printList(l) // a b c
    l.MoveToFront(l.Back())
    printList(l) // c a b
    l.Remove(l.Back())
    printList(l) // c a
}
func printList(l *list.List) {
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Print(e.Value, " ")
    }
    fmt.Println()
}

遍歷鏈表也很簡(jiǎn)單，不斷從 front 拿到元素，賦值為 Next，持續(xù)下去，直到 Next 為 nil，說(shuō)明遍歷結(jié)束，參照這里的 printList 即可。

結(jié)語(yǔ)

其實(shí) container/list 不僅僅給我們展示了一個(gè)比較規(guī)范標(biāo)準(zhǔn)的雙向鏈表實(shí)現(xiàn)，而且也廣泛應(yīng)用于很多業(yè)務(wù)場(chǎng)景，比如經(jīng)典的 groupcache 底層的 LRU 就是依靠 container/list 的能力，我們下一篇文章會(huì)分析一下。

以上就是深入了解Golang官方container/list原理的詳細(xì)內(nèi)容，更多關(guān)于Golang container/list的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: