list 套件


如果想連續地看待一組資料,可以使用 slice,優點是可以透過索引快速存取,透過 append 也可以附加元素,若偶而需要安插、刪除元素,可以透過切片等操作來實現。

然而,如果經常性地需要安插、刪除元素,透過 slice 實現缺乏效率時,Go 提供了 container/list 套件,可讓開發者基於雙向鏈結的 list.List 實作來達成需求。

想要建立 list.List 實例,可以透過 list.New,實例可使用的方法有:

func (l *List) Back() *Element
func (l *List) Front() *Element
func (l *List) Init() *List
func (l *List) InsertAfter(v interface{}, mark *Element) *Element
func (l *List) InsertBefore(v interface{}, mark *Element) *Element
func (l *List) Len() int
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)
func (l *List) PushBack(v interface{}) *Element
func (l *List) PushBackList(other *List)
func (l *List) PushFront(v interface{}) *Element
func (l *List) PushFrontList(other *List)
func (l *List) Remove(e *Element) interface{}

PushBackPushFront 方法的參數型態 interface{} 就能知道,list.List 可以保存任意型態的資料,它們會傳回 *ElementElement 是個結構,公開的欄位有 Value,公開的方法為 NextPrev

type Element struct {
    Value interface{}
}

func (e *Element) Next() *Element

func (e *Element) Prev() *Element

因此,若你保留傳回的 *Element,可以透過 Value 取得放入 list.List 的值,必要時也可以透過 NextPrev 方法,往後探尋下一元素或往前探尋前一元素,NextPrev 方法傳回的也是 *Element,因此隨時可以往前探尋元素前或後全部的清單。

BackFront 方法,分別傳回 list.List 最後、最前一個元素,因此,若要從清單頭走訪至尾,基本的模式就是:

package main

import (
    "fmt"
    "container/list"
)

func printAll(lt *list.List) {
    for e := lt.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }
}

func main() {
    lt := list.New()
    for i := 1; i <= 10; i++ {
        lt.PushBack(i)
    }

    printAll(lt)
}

你可能會有問題,ElementValue 型態是 interface{},那麼想操作保存的元素值上的欄位、方法時,不就要知道型態嗎?就目前來說,Go 不支援泛型,必須透過型態斷言:

package main

import (
    "fmt"
    "container/list"
)

type Person struct {
    Name string
    Age  int
}

func printAllPerson(persons *list.List) {
    for e := persons.Front(); e != nil; e = e.Next() {
        p := e.Value.(*Person)
        fmt.Printf("姓名:%s\t年齡:%d\n", p.Name, p.Age)
    }
}

func main() {
    persons := list.New()

    persons.PushBack(&Person{"Irene", 12})
    persons.PushBack(&Person{"Justin", 45})
    persons.PushBack(&Person{"Monica", 42})

    printAllPerson(persons)
}

你可能還會有其他問題,例如 list.List 怎麼不支援索引?要怎麼進行排序等?…唔…list.List 提供的方法怎麼這麼少?

嚴格來說,不會直接使用 list.List 來保存資料,而是如果某資料結構底層需要雙向鏈結的特性,可以透過 list.List 來實現。例如,實現一個 PersonQueue

package main

import (
    "fmt"
    "container/list"
)

type Person struct {
    Name string
    Age  int
}

type PersonQueue struct {
    list *list.List
}

func NewPersonQueue() *PersonQueue {
    return &PersonQueue{list.New()}
}

func (q *PersonQueue) Len() int {
    return q.list.Len()
}

func (q *PersonQueue) Offer(p *Person) {
    q.list.PushBack(p)
}

func (q *PersonQueue) Peek() *Person {
    if q.list.Len() == 0 {
        return nil
    }

    e := q.list.Remove(q.list.Front())
    return e.(*Person)
}

func main() {
    q := NewPersonQueue()

    q.Offer(&Person{"Irene", 12})
    q.Offer(&Person{"Justin", 45})
    q.Offer(&Person{"Monica", 42})

    for p := q.Peek(); p != nil; p = q.Peek() {
        fmt.Printf("姓名:%s\t年齡:%d\n", p.Name, p.Age)
    }
}

因此,並不是 list.List 不常用,而是你可能很少自行實現資料結構(都拿別人寫好的來用?);另一種說法「每當想使用 list.List 時,都該思考一下是否優先使用 slice。」的說法也不是完全正確…

若想使用 list.List,應該問的是,你的資料結構在實現上需要雙向鏈結的特性嗎?例如,也許你會需要有個具索引的資料結構,同時底層實現必須是雙向鏈結(像是 Java 的 LinkedList)?那麼就可以考慮透過 list.List 來實現。