C#双方向リスト(LinkedList)を試す。

.NETのAPIを眺めていたらLinkedListを見つけました。
データを格納するコンテナの一種なのですが、インデックスで要素にアクセスするList<>ともキーでアクセスするDictionary<>とも異なります。
サンプルプログラムを作成してみましたので動作確認をしてみたいと思います。

実行可能サンプル

// 
// LinkedListのサンプル
// 
using System;
using System.Collections.Generic;
using System.Linq;

using System.IO;

using System.Text.RegularExpressions;


// コンパイル
// csc LinkedList.cs

class LinkedListSample
{
    // エントリーポイント
    static void Main()
    {
        var path = @".\test";

        // ファイルの一覧を取得
        var files = Directory.EnumerateFiles(path);

        // IEnumerable<string>で初期化
        var linklist = new LinkedList<string>(files);
        
        // 先頭の要素を取得
        var node = linklist.First;
        Console.WriteLine("First:{0}", node.Value);
        // First:.\test\1.txt

        // 先頭か確認
        Console.WriteLine("isFirst:{0}", (node.Previous == null));
        // isFirst:True

        // 次の要素に移動
        node = node.Next;
        Console.WriteLine("Next:{0}", node.Value);
        // Next:.\test\2.txt

        // 要素の追加
        linklist.AddBefore(node, @".\test\1_5.txt");
        Console.WriteLine("要素の追加");
        foreach(var n in linklist)
        {
            Console.WriteLine("{0}", n);
        }
        // 要素の追加
        // .\test\1.txt
        // .\test\1_5.txt
        // .\test\2.txt
        // .\test\3.txt
        // .\test\4.txt
        // .\test\5.csv

        // 要素の変更
        node.Value = "Delete";
        Console.WriteLine("要素の変更");
        foreach(var n in linklist)
        {
            Console.WriteLine("{0}", n);
        }
        // 要素の変更
        // .\test\1.txt
        // .\test\1_5.txt
        // Delete
        // .\test\3.txt
        // .\test\4.txt
        // .\test\5.csv

        // 要素の検索
        node = linklist.Find("Delete");
        Console.WriteLine("Find:{0}", node.Value);
        // Find:Delete

        // 要素の削除
        linklist.Remove(node);
        Console.WriteLine("要素の削除");
        foreach(var n in linklist)
        {
            Console.WriteLine("{0}", n);
        }
        // 要素の削除
        // .\test\1.txt
        // .\test\1_5.txt
        // .\test\3.txt
        // .\test\4.txt
        // .\test\5.csv

        // 逆順のループ
        Console.WriteLine("逆順ループ");
        for(node = linklist.Last; node != null; node = node.Previous)
        {
            Console.WriteLine("{0}", node.Value);
        }
        // 逆順ループ
        // .\test\5.csv
        // .\test\4.txt
        // .\test\3.txt
        // .\test\1_5.txt
        // .\test\1.txt        

        // 要素のクリア
        linklist.Clear();
        Console.WriteLine("Any:{0} Count:{1}", linklist.Any(), linklist.Count());
        // Any:False Count:0

    }
}

LinkedListは機能としてのインデックスが無く、要素へのアクセスはLinkedListNodeオブジェクトを介して行います。LinkedListNodeには値を持つ.Valueプロパティ、次のノードを指す.Next、前のノードを指す.Previousがあります。.Next又は.PreviousをたどることでLinkedList全体の要素にアクセスすることが出来ます。
またLinqで操作することが出来ますしforeachでループを回すことも出来ます。ループというとサンプルに記載しましたが、要素を並べ替えることなく逆順のループをシンプルに記述できます。

思い出話になりますが、学習のため双方向リストをC言語で作成したことがありました。その当時使っていたC言語では基本固定長配列のみで、可変長なデータを扱いたい場合メモリを確保と解放を自前でプログラミングする必要がありました。
実装としてはLinkedListNodeの.Nextと.PreviosをLinkedListNodeへのポインタで表現します。各ノードを数珠繋ぎすることでコンテナを表現していました。要素の削除や追加は.Nextと.Previosの置き換えるだけで処理可能ですので、要素数が多くなっても一定のパフォーマンスを保つことが出来ました。また、先頭のノードと末尾のノードをつなげることでループ構造を作ることも出来ました。（使い道は思いつきませんでしたが…）

今時、双方向リスト(LinkedList)や連想配列(Dictionary)を実装して学習することも無いとは思いますが、構造を知らないと使い道が思いつかないような気もします。とくにLinkedListはインデックスがないちょっと不自由な配列の様にも見えます。
配列やListでも要素の追加や削除をすることも出来ますが、内部的にインデックスの再構築を行っているはずですし場合によっては、削除や追加の都度全体の再作成を行っている可能性もあります。そうなると要素数が多くなるとパフォーマンスが低下すると考えられます。
その点LinkedListは要素同士の繋ぎ変えで追加や削除機能を実現していますので、要素が多くなっても安定したパフォーマンスを期待できます。

List<T>やDictionary<T>と比べ使用頻度は低いかもしれませんが、用途によっては、かなり使えるコンテナだと思います。

実行可能サンプル

コメント