Go 言語標準ライブラリの container/list を deque として使ってみた
はじめに
お疲れ様です．ぬまっちです．先日 AtCoder の競プロ典型 90 問の問題 43 を解いていたのですが，解いている最中に「C++の deque に対応する操作を Golang でやりたいときってどうすればいいんだっけ？」と疑問に思い，調べてみました．
キューとスタックはスライスで実現できますが，deque はスライスで実現したくありませんでした．先頭への要素追加時にスライスの全要素を処理する必要があり，
deque := make([]int, 0)
deque = append(deque, 1) // push_back O(1)
deque = append(deque, -3) // push_back O(1)
deque = append([]int{2}, deque...) // push_front O(N)
リンクリストを自作することも考えましたが，なんと標準ライブラリに双方向のリンクリスト (doubly linked list) があることが分かった [1] ので，こちらを deque として使ってみました．この記事では，こちらの container/list でよく利用しそうな関数について，その使い方を整理しようと思います．
使い方
初期化
まずは初期化です．container/list をインポートして，New 関数で初期化します．
import (
"container/list"
)
func ExampleDeque() {
deque := list.New() // 双方向の連結リストを生成
}
ここで，New 関数は上記 container/list パッケージで定義された List 構造体へのポインタを返却します．この構造体のメソッドとして，先頭・末尾要素の追加・削除等が定義されています．
先頭・末尾への要素の追加
先頭への要素の追加には PushFront を，末尾への要素追加には PushBack を利用します．
ここで，PushFront と PushBack の引数は interface{} 型となっているので，int や string だけでなく構造体も追加することができます．
// 先頭に要素を追加する
deque.PushFront(-5) // [-5]
deque.PushFront(10) // [10, -5]
// 末尾に要素を追加する
deque.PushBack(3) // [10, -5, 3]
deque.PushBack(-1) // [10, -5, 3, -1]
先頭・末尾要素の取得
先頭要素の取得には Front を，末尾要素の取得には Back を利用します．これらの関数は container/list で定義されている Element 構造体のポインタを返却します．
Element 構造体は，連結リストの前の要素へのポインタ prev，後の要素へのポインタ next，所属する連結リストへのポインタ list，現在の要素の値 Value を保持しています．
参考までに，以下は標準ライブラリの Element 構造体の実装です．
package list
// 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{}
}
先頭・末尾要素の値を取得するためには，Front や Back で返却された Element に対して Value でアクセスする必要があります．
// deque: [10, -5, 3, -1] とする
// 先頭要素を取得
v1 := deque.Front().Value // 10
// 末尾要素を取得
v2 := deque.Back().Value // -1
以下は補足ですが，Value は interface{} 型なので，上記のように値を取得するだけでなく，取得した要素が持つ属性やメソッドにアクセスしたい場合，以下のようにキャストする必要があるので注意が必要です．
// この構造体をdequeに格納しているとして
type node struct {
x, y, dir int
}
deque.PushBack(node{1, 1, 1})
// ... 中略
// 属性にアクセスしたいならキャストが必要
e := deque.Front().Value.(node)
fmt.Println(e.x + e.y) // 2
先頭・末尾要素の削除
ここは C++とインタフェースが異なります．
C++では pop_xxx が実装されていますが，container/list では「先頭要素の削除」「末尾要素の削除」専用の関数は準備されていません．
代わりに，引数として渡された Element を削除し，削除した要素を返却する関数 Remove が準備されています．より一般的ですね．
Remove と Front，Back を併用すると，C++の pop_xxx を実現できます．
// deque: [10, -5, 3, -1] とする
// 先頭要素を削除 (pop_frontと同等)
deque.Remove(deque.Front()) // 10の*Elementを返却, deque: [-5, 3, -1]
// 末尾要素を削除 (pop_backと同等)
deque.Remove(deque.Back()) // -1の*Elementを返却, deque: [-5, 3]
リストの走査
container/list が提供する deque は双方向のリンクリストによって実装されており，i 番目の要素へのランダムアクセスはできません．
i 番目の要素を取得したい場合も，リスト全体を走査するときも，計算量としては
deque の先頭から末尾までの走査は以下のように書けます．
// deque: [5, 3, -1] とする
// 先頭から順に走査したい場合にはNextを利用する
for e := deque.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value) // 5, 3, -1の順に出力される
}
最後の要素は次の要素へのポインタとして nil を持っているはずなので，そこで走査が終了します．また，Next は Element が保持する次要素へのポインタを返却します．
同様に，末尾から先頭までの走査は以下のように書けます．
// deque: [5, 3, -1] とする
// 末尾から順に走査したい場合にはPrevを利用する
for e := deque.Back(); e != nil; e = e.Prev() {
fmt.Println(e.Value) // -1, 3, 5の順に出力される
}
deque の要素が存在しなくなるまでループ処理をしたい場合，Len で deque の長さを取得できるので，その長さが 0 より大きい間ループさせればよいです．
// dequeの要素が無くなるまで処理をしたいときはLenで判定できる
for deque.Len() > 0 {
e := deque.Remove(deque.Front())
// 要素eを用いた処理...
}
その他
上記以外にも，特定要素の前後への要素追加等できるので，気になる方は公式ドキュメントをご参照ください．
具体例
deque の練習問題として，以下の AtCoder の問題を解いてみました．
先頭と末尾のどちらから追加すべきかを適切に場合分けできれば，後は container/listを deque として用いて簡単に解くことができます．
走査の際に，Next や Prev の値を調べることで，走査の最後かどうかを判定しています．(半角スペース追加のため)
注意点
例えば 競プロ典型 90 問 061 - Deck（★2） のような問題では，
前述の通り，container/list では任意の要素へランダムアクセスできないことから，全体の計算量が
終わりに
以上，Go 言語標準ライブラリの container/list の使い方でした．名前がただの list なのでちょっと見つけづらいかもしれませんが，deque，双方向リンクリストとして利用できる優秀な標準ライブラリなので，是非覚えておきましょう．
-
Go では，セット，スタック，キューといった標準的なデータ構造がその名前で提供されていません．セットなら
mapを，スタックとキューならsliceを用いることで，各データ構造を再現できます．調べ始めたときは，これらと同じくslice使ってやらないといけなかったら嫌だなー考えながら調べてました． ↩︎
Discussion