おそらく、上記に基づいたNodeの一般的なクラスとLinkedListのクラスがあり、ユーザーが追加、削除などを行うことができます。では、どのようにして不変性を確保するのでしょうか。
オブジェクトのすべてのフィールドを読み取り専用にし、それらの読み取り専用フィールドの1つによって参照されるすべてのオブジェクトも不変オブジェクトであることを確認することで、不変性を確保します。フィールドがすべて読み取り専用で、他の不変データのみを参照している場合、明らかにオブジェクトは不変になります。
要素を挿入するときに、リストへのすべての参照を再帰的にコピーする必要がありますか？
あなたは出来る。ここで得られる違いは、不変と永続の違いです。不変のデータ構造は変更できません。永続データ構造は、データ構造が不変であるという事実を利用して、その部分を再利用します。
永続的な不変のリンクリストは特に簡単です。
abstract class ImmutableList
{
public static readonly ImmutableList Empty = new EmptyList();
private ImmutableList() {}
public abstract int Head { get; }
public abstract ImmutableList Tail { get; }
public abstract bool IsEmpty { get; }
public abstract ImmutableList Add(int head);
private sealed class EmptyList : ImmutableList
{
public override int Head { get { throw new Exception(); } }
public override ImmutableList Tail { get { throw new Exception(); } }
public override bool IsEmpty { get { return true; } }
public override ImmutableList Add(int head)
{
return new List(head, this);
}
}
private sealed class List : ImmutableList
{
private readonly int head;
private readonly ImmutableList tail;
public override int Head { get { return head; } }
public override ImmutableList Tail { get { return tail; } }
public override bool IsEmpty { get { return false; } }
public override ImmutableList Add(int head)
{
return new List(head, this);
}
}
}
...
ImmutableList list1 = ImmutableList.Empty;
ImmutableList list2 = list1.Add(100);
ImmutableList list3 = list2.Add(400);
そして、あなたは行きます。もちろん、より優れた例外処理と、メソッドなどのIEnumerable<int>メソッドを追加することをお勧めします。しかし、永続的な不変のリストがあります。新しいリストを作成するたびに、既存の不変リストの内容を再利用します。list3は、list2の内容を再利用します。これは、list2が変更されることはないため、安全に実行できます。
あなたの答えのどれかが二重にリンクされたリストでも機能しますか？
もちろん、データ構造全体の完全なコピーを毎回実行する二重リンクリストを簡単に作成できますが、それはばかげています。配列を使用して、配列全体をコピーすることもできます。
永続的な二重リンクリストを作成することは非常に困難ですが、それを行う方法はいくつかあります。私がすることは、反対方向から問題に取り組むことです。「永続的な二重リンクリストを作成できますか？」と言うのではなく、「私が魅力的だと思う二重リンクリストの特性は何ですか？」と自問してください。それらのプロパティを一覧表示してから、それらのプロパティを持つ永続データ構造を考え出すことができるかどうかを確認してください。
たとえば、二重リンクリストをどちらかの端から安価に拡張でき、2つのリストに安価に分割でき、2つのリストを安価に連結できるというプロパティが好きな場合、必要な永続構造は不変のcatenabledequeです。 、二重リンクリストではありません。ここに、不変の非対応の両端キューの例を示します。
http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx
それを拡張して受け入れ可能な両端キューにすることは、演習として残されています。私がリンクしているフィンガーツリーの紙は読むのに良いものです。
アップデート：
上記に従って、プレフィックスを挿入ポイントまでコピーする必要があります。不変性の論理により、wがプレフィックスから何かを削除すると、新しいリストとサフィックスが取得されます...なぜ、サフィックスではなく、プレフィックスのみをコピーするのでしょうか。
例を考えてみましょう。リスト（10、20、30、40）があり、位置2に25を挿入したい場合はどうなりますか？したがって、（10、20、25、30、40）が必要です。
どの部品を再利用できますか？手元にあるテールは（20、30、40）、（30、40）、（40）です。明らかに再利用できます（30、40）。
ダイアグラムを描くと役立つ場合があります。我々は持っています：
10 ----> 20 ----> 30 -----> 40 -----> Empty
そして私たちは欲しい
10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty
だから作りましょう
| 10 ----> 20 --------------> 30 -----> 40 -----> Empty
| /
| 10 ----> 20 ----> 25 -/
（30、40）は両方のリストに共通しているため、再利用できます。
アップデート：
ランダムな挿入と削除のコードも提供できますか？
再帰的な解決策は次のとおりです。
ImmutableList InsertAt(int value, int position)
{
if (position < 0)
throw new Exception();
else if (position == 0)
return this.Add(value);
else
return tail.InsertAt(value, position - 1).Add(head);
}
これが機能する理由がわかりますか？
ここで演習として、再帰的なDeleteAtを記述します。
ここで、演習として、非再帰的なInsertAtとDeleteAtを記述します。不変のリンクリストを自由に使用できるので、反復ソリューションで使用できることを忘れないでください。