Go言語（Golang）で双方向連結リスト（Doubly Linked List）を扱うcontainer/listパッケージについて

こんにちは。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

リストで使えるメソッド一覧

*list.Element型のフィールド

最後に

今回はGo言語（Golang）で双方向連結リスト（Doubly Linked List）を扱うcontainer/listパッケージについて解説しました。

リストの要素の途中などで頻繁に要素を追加・削除するような処理はスライスを使うと効率が悪く、またキュー（先に入れたものが先に出る）やスタック（最後に入れたものが最初に出る）のような要素の前後移動が必要になる場合は、双方向連結リストを使うのが最適です。

例えばブラウザの履歴管理における「戻る」「進む」ボタンの操作や、音楽のプレイリストにおける曲の再生順序の変更のような処理で双方向連結リストを使ったりするので覚えておきましょう。