6

これはより理論的な問題です。C# で真に不変の二重リンク リストを作成することは、どのような方法でも可能ですか? 私が見た問題は、隣接する 2 つのノードの相互依存関係にあります。

「本当に」とは、読み取り専用フィールドを使用することを意味します。

4

3 に答える 3

10

これは、トリッキーなコンストラクター ロジックで行うことができます。例えば

public sealed class Node<T> { 
  readonly T m_data;
  readonly Node<T> m_prev;
  readonly Node<T> m_next;

  // Data, Next, Prev accessors omitted for brevity      

  public Node(T data, Node<T> prev, IEnumerator<T> rest) { 
    m_data = data;
    m_prev = prev;
    if (rest.MoveNext()) {
      m_next = new Node(rest.Current, this, rest);
    }
  }
}

public static class Node {    
  public static Node<T> Create<T>(IEnumerable<T> enumerable) {
    using (var enumerator = enumerable.GetEnumerator()) {
      if (!enumerator.MoveNext()) {
        return null;
      }
      return new Node(enumerator.Current, null, enumerator);
    }
  }
}

Node<string> list = Node.Create(new [] { "a", "b", "c", "d" });
于 2012-05-25T15:45:36.643 に答える
4

あなたは私の好奇心をそそりました。ReadOnlyNodeのクラスは、以下を定義するのに十分単純です。

public class ReadOnlyNode<T>
{
   public readonly T Value;
   public readonly ReadOnlyNode<T> Next;
   public readonly ReadOnlyNode<T> Prev;

   public Node(T value, ReadOnlyNode<T> next, ReadOnlyNode<T> prev)
   {
      Value = value;
      Next = next;
      Prev = prev;
   }
}

二重リンクリストの問題はreadonly、ノードごとに、コンストラクター内でそのノードの前のノードと次のノードを指定する必要があるため、コンストラクターの外部から渡される場合は、それらがすでに存在している必要があることです。ただし、ノードMは、コンストラクターを呼び出すときに「次の」ノードとして既存のノードNを必要としますが、そのノードNは、構築されるために「前の」ノードとしてMを必要とします。これにより、NとMの両方が最初に他のノードをインスタンス化する必要がある「鶏が先か卵が先か」の状況が発生します。

ただし、この猫の皮を剥ぐ方法は複数あります。リストの各ノードが1つのReadOnlyNodeのコンストラクター内から再帰的にインスタンス化された場合はどうなりますか?各コンストラクターが完了するまで、各レベルのプロパティは変更可能であり、各ノードへの参照はコンストラクター内に存在するため、すべてがセットアップされるまですべてがセットアップされていなくてもかまいません。次のコードはコンパイルされ、既存のIEnumerableが与えられると、不変の二重リンクリストが生成されます。

public class ReadOnlyNode<T>
{
    public readonly T Value;
    public readonly ReadOnlyNode<T> Next;
    public readonly ReadOnlyNode<T> Prev;

    private ReadOnlyNode(IEnumerable<T> elements, ReadOnlyNode<T> prev)
    {
        if(elements == null || !elements.Any()) 
           throw new ArgumentException(
              "Enumerable must not be null and must have at least one element");
        Next = elements.Count() == 1 
           ? null 
           : new ReadOnlyNode<T>(elements.Skip(1), this);
        Value = elements.First();
        Prev = prev;
    }

    public ReadOnlyNode(IEnumerable<T> elements)
        : this(elements, null)
    {
    }
}


//Usage - creates an immutable doubly-linked list of integers from 1 to 1000
var immutableList = new ReadOnlyNode<int>(Enumerable.Range(1,1000));

これは、IEnumerableを実装する任意のコレクションで使用できます(ほとんどすべての組み込みコレクションで使用でき、OfType()を使用して、非汎用ICollectionおよびIEnumerableを汎用IEnumerableに変換できます)。心配するのはコールスタックだけです。ネストできるメソッド呼び出しの数には制限があり、有限であるが大量の入力リストでSOEが発生する可能性があります。

編集: JaredParは非常に良い点をもたらします。このソリューションは、Skip()の結果を考慮に入れる必要があるCount()とAny()を使用するため、コレクションクラスのカーディナリティプロパティを使用できるこれらのメソッドに組み込まれた「ショートカット」を使用できません。これらの呼び出しは線形になり、アルゴリズムの複雑さが二乗されます。代わりにIEnumerableの基本メンバーを使用する場合、これははるかにパフォーマンスが高くなります。

public class ReadOnlyNode<T>
{
    public readonly T Value;
    public readonly ReadOnlyNode<T> Next;
    public readonly ReadOnlyNode<T> Prev;

    private ReadOnlyNode(IEnumerator<T> elements, ReadOnlyNode<T> prev, bool first)
    {
        if (elements == null) throw new ArgumentNullException("elements");

        var empty = false;
        if (first) 
           empty = elements.MoveNext();

        if(!empty)
        {
           Value = elements.Current;
           Next = elements.MoveNext() ? new ReadOnlyNode<T>(elements, this, false) : null;
           Prev = prev;
        }
    }

    public ReadOnlyNode(IEnumerable<T> elements)
        : this(elements.GetEnumerator(), null, true)
    {
    }
}

このソリューションを使用すると、より洗練されたエラーチェックが少し失われますが、IEnumerableがnullの場合、とにかく例外がスローされます。

于 2012-05-25T16:50:10.483 に答える
2

はい、リンクの設定に使用する「リンクセッター」オブジェクトを作成して、ノードのコンストラクターに送信するか、「リンクセッター」を返す静的作成メソッドを使用できます。ノード内のリンクは非公開であり、「リンクセッター」を介してのみアクセスできます。それらを使用してリストを設定したら、それらを破棄します。

しかし、それはかなり無駄な練習です。リストが不変の場合、単純な配列の方が適切に機能する場合、二重リンク リストを使用しても意味がありません。

于 2012-05-25T15:46:21.997 に答える