Golang listパッケージを使ったdoubly linked listの操作

Golang listという標準パッケージを使ってdoubly linked listの操作を簡単に行えるので、まとめます。

使い方

listパッケージを使うためには、公式ドキュメントにある通り、"container/list"をインポートします。

list.New()で新たなlistインスタンスを生成する事ができます。

http://golang-jp.org/pkg/container/list/#New

func New() *List

List構造体とListがもつ要素を表すElement構造体は、以下のようなデータ構造となります。

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

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

List構造体は、Element型のroot要素を一つもつのと、List自体の長さを表すlenを持ちます。
そしてElement構造体は、要素自身がもつ値Valueと、自分が属するListのポインタ Listと、さらには、自分の要素の前・後に位置する要素のポインタ next, prevを持ちます。

List Element構造体を使って、他の言語でもよく見られる一般的なdoubly linked listの構造をあらわしています。

package main

import (
    "container/list"
    "fmt"
)

func main() {
    // create a new list
    l := list.New()
    l.PushBack(1) // l {1}

    // list mに要素を2つ追加
    m := list.New()
    m.PushBack(2) // m {2}
    m.PushBack(3) // m {2, 3}
    fmt.Printf("Length of m is %d\n", m.Len())

    // lの後ろにmをつなげる
    l.PushBackList(m)

    // Iterate through list and print its contents.
    // 1 2 3と表示される
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }

    // l の先頭に要素追加
    l.PushFront(5) // l {5, 1, 2, 3}

    // l の先頭にmの要素をつなげる
    l.PushFrontList(m) // l {2, 3, 5, 1 , 2, 3}

    // Iterate through list and print its contents.
    // 2 3 5 1 2 3 と表示される
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }

    // 最後の要素を削除する
    l.Remove(l.Back())
    // Iterate through list and print its contents.
    // 2 3 5 1 2 と表示される
    for e := l.Front(); e != nil; e = e.Next() {
        fmt.Println(e.Value)
    }

}

非常に簡単に使えます。
Goに関しては勉強中で、サードパーティのコレクションライブラリなどもあるかどうかは調べれてないですが、
listパッケージを使って問題なくdoubly linked listを利用できます。

kakts-log

programming について調べたことを整理していきます

Golang listパッケージを使ったdoubly linked listの操作

使い方