how can I create a truly immutable doubly linked list in C#?

Question

It is more of a theoretical question: Is it possible by any means in C# to create a truly immutable doubly linked list? A problem as I see it is in the mutual dependency of 2 adjacent nodes.

By "truly" I mean using readonly fields.

Answer 1

This is possible to do with tricky constructor logic. For example

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

You piqued my curiousity. The class for a ReadOnlyNode is simple enough to define:

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

The problem with readonly in a doubly-linked list is that, for each node, you have to specify that node's previous and next nodes in the constructor, so if they're passed from outside the constructor they must already exist. But, Node M needs a pre-existing Node N as its "next" node when you call the constructor, but that node N needs M as its "previous" node in order to be constructed. This creates a "chicken and egg" situation where both N and M need the other node to be instantiated first.

However, there's more than one way to skin this cat. What if each node of a list was instantiated recursively from within the constructor of one ReadOnlyNode? Until each constructor was complete, the properties at each level would still be mutable, and the reference to each Node would exist in its constructor, so it wouldn't matter that not everything had been set up until everything is set up. The following code compiles, and given a pre-existing IEnumerable will produce an immutable doubly-linked list:

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

You can use this with any collection that implements IEnumerable (pretty much all built-in collections do, and you can use OfType() to turn non-generic ICollections and IEnumerables into generic IEnumerables). The only thing to worry about is the call stack; there is a limit to how many method calls you can nest, which may cause an SOE on a finite but large list of inputs.

EDIT: JaredPar brings up a very good point; this solution uses Count() and Any() which have to take the results of Skip() into account, and so cannot use the "shortcuts" built into these methods that can use the cardinality property of a collection class. Those calls become linear, which squares the complexity of the algorithm. If you just use the basic members of IEnumerable instead, this becomes much more 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)
    {
    }
}

With this solution, you lose a little of the more elegant error-checking, but if the IEnumerable is null an exception would have been thrown anyway.

Answer 3

Yes, you can make a "link-setter" object used for setting the links, that you send into the constructor of the node, or have a static create method that returns the "link-setter". The links in the node are private, and can only be accessed through the "link-setter", and when you have used them to set up the list, you throw them away.

However, that's a pretty useless exercise. If the list is immutable, it's pointless to use a doubly linked list when a simple array works better.