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

C# コンピュータ
C#

ファイルの一覧から特定のファイルから見た次のファイルや前のファイルを取得する場合、配列やList<T>などでファイルの一覧を表現するとインデックスの管理が面倒だったりします。また配列やList<T>の場合途中に要素を追加したり削除することが難しく、出来たとしても効率が悪いと言われています。
そういった場合、双方向リスト(LinkedList)を使うと少し便利です。

スポンサーリンク

実行可能サンプル

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

コメント