Wie kann ich eine wirklich unveränderliche doppelt verknüpfte Liste in C# erstellen?

Question

Es ist eher eine theoretische Frage: Ist es in C# überhaupt möglich, eine wirklich unveränderliche doppelt verknüpfte Liste zu erstellen? Ein Problem, wie ich es sehe, liegt in der gegenseitigen Abhängigkeit von zwei benachbarten Knoten.

Mit "wirklich" meine ich mit readonly Felder.

Answer 1

Dies ist möglich, mit kniffligen Konstruktor Logik zu tun. Zum Beispiel

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" }); 

Answer 2

Ja, können Sie ein „Link-Setter“ Objekt machen für die Einstellung der Links verwendet, die Sie in den Konstruktor des Knotens senden, oder haben eine statische Methode erstellen, die den „Link-Setter zurück ". Die Links im Knoten sind privat und können nur über den "Link-Setter" erreicht werden. Wenn Sie sie zum Einrichten der Liste verwendet haben, werfen Sie sie weg.

Allerdings ist das eine ziemlich nutzlose Übung. Wenn die Liste unveränderlich ist, ist es sinnlos, eine doppelt verknüpfte Liste zu verwenden, wenn ein einfaches Array besser funktioniert.

Answer 3

Sie pikante meine Neugier. Die Klasse für einen ReadOnlyNode ist einfach genug zu definieren:

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; 
    } 
} 

Das Problem mit readonly in einer doppelt verketteten Liste ist, dass für jeden Knoten, müssen Sie dieses Knotens der vorherigen und nächsten Knoten im Konstruktor angeben, so Wenn sie von außerhalb des Konstruktors übergeben werden, müssen sie bereits existieren. Knoten M benötigt jedoch einen bereits existierenden Knoten N als seinen "nächsten" Knoten, wenn Sie den Konstruktor aufrufen, aber dieser Knoten N benötigt M als seinen "vorherigen" Knoten, um konstruiert zu werden. Dies erzeugt eine "Hühner- und Ei" -Situation, in der sowohl N als auch M den anderen Knoten benötigen, der zuerst instantiiert werden soll.

Allerdings gibt es mehr als eine Möglichkeit, diese Katze zu häuten. Was passiert, wenn jeder Knoten einer Liste rekursiv aus dem Konstruktor eines ReadOnlyNode instanziiert wird? Bis jeder Konstruktor fertig war, wären die Eigenschaften auf jeder Ebene noch änderbar und der Verweis auf jeden Knoten würde in seinem Konstruktor existieren, so dass es nicht wichtig wäre, dass nicht alles eingerichtet wurde, bis alles eingerichtet ist. Der folgende Code kompiliert, und angesichts einer bereits bestehenden IEnumerable wird eine unveränderliche doppelt verkettete Liste erzeugen:

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)); 

Sie können dies mit einer beliebigen Sammlung verwenden, die IEnumerable implementiert (so ziemlich alle Sammlungen in integrierten tun, und Sie kann OfType() verwenden, um nicht generische ICollections und IEnumerables in generische IEnumerables umzuwandeln. Das einzige, worüber man sich Sorgen machen muss, ist der Call-Stack; Es gibt eine Grenze für die Anzahl der Methodenaufrufe, die Sie verschachteln können. Dies kann zu einer SOE auf einer endlichen, aber großen Liste von Eingängen führen.

EDIT: JaredPar bringt einen sehr guten Punkt; Diese Lösung verwendet Count() und Any(), die die Ergebnisse von Skip() berücksichtigen müssen, und kann daher nicht die in diesen Methoden integrierten "Verknüpfungen" verwenden, die die Kardinalitätseigenschaft einer Auflistungsklasse verwenden können. Diese Aufrufe werden linear, wodurch sich die Komplexität des Algorithmus vervierfacht. Wenn Sie stattdessen einfach die grundlegenden Elemente von IEnumerable verwendet, wird dies viel mehr performant:

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) 
    { 
    } 
} 

Mit dieser Lösung, verlieren Sie ein wenig von der elegantere Fehlerprüfung, aber wenn der IEnumerable ist eine Null-Ausnahme hätte wurde sowieso geworfen.