こんにちは。Tomoyuki（@tomoyuki65）です。
Go言語（Golang）で複数の要素を扱う際はスライスなどを使いますが、処理内容によっては双方向連結リスト（Doubly Linked List）を使った方がいい可能性があります。
双方向連結リストというのは、データの並びを格納するためのデータ構造の一つであり、各要素（ノード）が前後の要素を互いに参照できるようになっているリストで、Go言語ではcontainer/listパッケージを使うことで簡単に扱うことができます。
この記事では、そんなcontainer/listパッケージについてご紹介します。
Go言語（Golang）で双方向連結リスト（Doubly Linked List）を扱うcontainer/listパッケージについて
まずはリストを作成し、そのリストの末尾に要素を追加するには「PushBack」、またはリストの先頭に要素を追加するには「PushFront」を使います。
package main
import (
"container/list"
"fmt"
)
func main() {
// リストの作成
l := list.New()
// リストの末尾に2回要素を追加
l.PushBack(1)
l.PushBack(10)
// リストの先頭に1回要素を追加
l.PushFront(5)
// リストの先頭の要素から一つずつ取り出してログ出力
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
実行結果
5
1
10
また、二つ目の要素の次に要素を追加したいような場合は「InsertAfter」を使います。
package main
import (
"container/list"
"fmt"
)
func main() {
// リストの作成
l := list.New()
// リストの末尾に2回要素を追加
l.PushBack(1)
l.PushBack(10)
// リストの先頭に1回要素を追加
l.PushFront(5)
// 2つ目の要素を取得
second := l.Front().Next()
// 2つ目の要素の次に要素を追加
l.InsertAfter(100, second)
// リストの先頭の要素から一つずつ取り出してログ出力
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
実行結果
5
1
100
10
リストで使えるメソッド一覧
| メソッド | 説明 |
|---|---|
| Init() *List | リストを空に初期化して、リスト自身を返す |
| Len() int | リスト内の要素数を返す |
| Front() *Element | リストの先頭要素を返す。要素がなければ nil |
| Back() *Element | リストの末尾要素を返す。要素がなければ nil |
| PushFront(v interface{}) *Element | 新しい要素をリストの先頭に追加し、その要素を返す |
| PushBack(v interface{}) *Element | 新しい要素をリストの末尾に追加し、その要素を返す |
| InsertBefore(v interface{}, mark *Element) *Element | 指定した要素 mark の前に新しい要素を挿入し、その要素を返す |
| InsertAfter(v interface{}, mark *Element) *Element | 指定した要素 mark の後に新しい要素を挿入し、その要素を返す |
| Remove(e *Element) interface{} | 指定した要素をリストから削除し、削除した要素の値を返す |
*list.Element型のフィールド
| フィールド | 説明 |
|---|---|
| Value | 要素が持つ値（interface{} 型） |
| Next | リストの次の要素（*Element 型）。末尾の場合は nil |
| Prev | リストの前の要素（*Element 型）。先頭の場合は nil |
最後に
今回はGo言語（Golang）で双方向連結リスト（Doubly Linked List）を扱うcontainer/listパッケージについて解説しました。
リストの要素の途中などで頻繁に要素を追加・削除するような処理はスライスを使うと効率が悪く、またキュー（先に入れたものが先に出る）やスタック（最後に入れたものが最初に出る）のような要素の前後移動が必要になる場合は、双方向連結リストを使うのが最適です。
例えばブラウザの履歴管理における「戻る」「進む」ボタンの操作や、音楽のプレイリストにおける曲の再生順序の変更のような処理で双方向連結リストを使ったりするので覚えておきましょう。
コメント