原本打算用Go實(shí)現(xiàn)Java中常見的集合，簡單實(shí)現(xiàn)ArrayList后，之后翻官網(wǎng)的package,發(fā)現(xiàn)了
container/list，發(fā)現(xiàn)其實(shí)現(xiàn)十分的簡潔，所以學(xué)習(xí)記錄如下:
List實(shí)現(xiàn)準(zhǔn)備工作
如果想實(shí)現(xiàn)一個(gè)list，首先想到解決問題：
- 數(shù)據(jù)類型怎么處理？
- Go中有沒有像Java中Object似的，萬能的數(shù)據(jù)類型呢？
多虧Go中存在interface{}這樣萬能的數(shù)據(jù)類型，問題就迎刃而解啦！
來看看我的ArrayList實(shí)現(xiàn)設(shè)計(jì):
type ArrayList struct {
size int32
data []interface{}
}
我利用slice來實(shí)現(xiàn)簡單的list(單向鏈表)操作，再看看官網(wǎng)的實(shí)現(xiàn):
type Element struct {
prev, next *Element
list *List
Value interface{}
}
type List struct {
root Element
len int
}
哈哈，這么一對比，我都有些害羞啦！官網(wǎng)上更面向?qū)ο蠡?，?code>List中元素抽象成了Element，Element并存在自己讀取前后節(jié)點(diǎn)的方法。
Element中獲取操作
- 獲取自身的Value
- 獲取前驅(qū)節(jié)點(diǎn)
- 獲取后繼節(jié)點(diǎn)
Go的特點(diǎn)之一就是，其訪問權(quán)限用首字母大小寫來區(qū)分，Element可以直接獲取其Value，而前后節(jié)點(diǎn)則分別提供了方法：
func (e *Element) Next() *Element {
if p := e.next; e.list != nil && p != &e.list.root {
return p
}
return nil
}
func (e *Element) Prev() *Element {
if p := e.prev; e.list != nil && p != &e.list.root {
return p
}
return nil
}
好不好奇，為什么類型是*Element? 當(dāng)然是修改其值啦！
指針傳遞對象的引用，而非指針則是對對象的copy，指針使用規(guī)則如下:
- 只要需要修改對象的時(shí)候，才必須使用指針，它不是Go語言的約束，而是一種自然約束。
- 有時(shí)對象很小，用指針傳遞并不劃算
List的初始化
List通過調(diào)用New()方法來初始化一個(gè)list，New()方法實(shí)現(xiàn)如下代碼，Init()中將root.next,root.prev全都指向了root，這將在為下面的實(shí)現(xiàn)做鋪墊
//Init initializes or clears list l
func (l *List) Init() *List {
l.root.next = &l.root // next ---> root
l.root.prev = &l.root // next ---> root
//l.root.list = l //
l.len = 0
return l
}
func New() *List {
//new 申請內(nèi)存初始化
list := new(List)
return list.Init()
}
執(zhí)行完上New()后，會產(chǎn)生一個(gè)類似{{0x000001, 0x000001, nil, nil}, 0}對象（0x000001只是個(gè)栗子），然而這個(gè)地址就是Element.list，保證list中的一致性。
List中的存儲操作
List中的存儲操作方法如下:
- func (l *List) InsertAfter(v interface{}, mark *Element) *Element ：在mark元素后添加元素
- func (l *List) InsertBefore(v interface{}, mark *Element) *Element：在mark元素前添加元素
- func (l *List) PushBack(v interface{}) *Element ：在list尾添加元素
- func (l *List) PushBackList(other *List)：在list尾添加元素列表
- func (l *List) PushFront(v interface{}) *Element ：在list頭添加元素
- func (l *List) PushFrontList(other *List)：在list頭添加元素列表
如上這些公開的方法都是建立在insert(e, at *Element)和insertValue(v interface{}, at *Element)方法之上的，代碼如下：
//insert e after at
func (l *List) insert(e, at *Element) *Element {
n := at.next
at.next = e
e.prev = at
e.next = n
n.prev = e
e.list = l
l.len++
fmt.Println("l.root.prev:", l.root.prev, " l.root.next:", l.root.next)
return e
}
func (l *List) insertValue(v interface{}, at *Element) *Element {
//創(chuàng)建新的節(jié)點(diǎn)
return l.insert(&Element{Value: v}, at)
}
需要說明的是，insert(e, at *Element)實(shí)現(xiàn)是將e放到at后面啦，這對理解后面的代碼很有幫助。
附上PushBack(v interface{})流程圖：
由于
PushFront(v interface{})執(zhí)行過程與PushBack(v interface{})相反，所以附上其圖如下，仔細(xì)觀察，便知道其區(qū)別:
假設(shè)上面Element的地址分別為0x001,0x002,0x003，分別將2,3放入列表中.
如上方法實(shí)現(xiàn)很簡單，都在建立"insertValue(v interface{}, at *Element)"之上的，所以不在文章中貼代碼啦！
List中的獲取操作
- func (l *List) Back() *Element ：獲取最后節(jié)點(diǎn)
- func (l *List) Front() *Element：獲取第一個(gè)節(jié)點(diǎn)
一開始初始化的節(jié)點(diǎn)，就是存放頭結(jié)點(diǎn)和尾節(jié)點(diǎn)指針用的，所以Back()操作返回其l.root.prev，Front()操作返回其l.root.next就搞定啦！
List中的刪除操作
然而上述方法內(nèi)部調(diào)用了remove(e *Element)， 代碼如下:
func (l *List) remove(e *Element) *Element {
e.prev.next = e.next
e.next.prev = e.prev
//avoid memory leaks
e.prev = nil
e.next = nil
e.list = nil
l.len--
return e
}
該方法的作用就是修改需要刪除節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)，最后將其前后節(jié)點(diǎn)指針置空，防止內(nèi)存異常。
List中的移動操作
- func (l *List) MoveAfter(e, mark *Element)
- func (l *List) MoveBefore(e, mark *Element)
- func (l *List) MoveToBack(e *Element)
- func (l *List) MoveToFront(e *Element)
所以移動操作，都是借助insertValue(v interface{}, e *Element)和remove(e *Element)方法搞定的，使用的真是巧妙，具體查看源碼吧！
注意：list不是協(xié)程安全的。
總體來說，通過翻閱list源碼，掌握了它代碼實(shí)現(xiàn)的list存儲結(jié)構(gòu)，更體會到了OOD的思想！(這篇文章，主要就是上面的兩張圖)
