How can I create a truly immutable double list in C #?

Question

This is rather a theoretical question: is it possible in any way in C # to create a truly immutable doubly linked list? The problem, as I see it, is related to the interdependence of two neighboring nodes.

By true I mean using readonly fields.

Answer 1

This can be done using complex constructor logic. for instance

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 struck my curiosity. The class for 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 need to indicate that the node is the previous and next nodes in the constructor, so if they are passed from outside the constructor, they must already exist. But, node M needs the pre-existing node N as the “next” node when calling the constructor, but node N requires M as its “previous” node in order to be built. This creates a chicken and egg situation, where both N and M need the second node to be created first.

However, there is more than one way to trick this cat. What if each list node was recursively created from the constructor of a single ReadOnlyNode? Until each constructor is complete, the properties at each level will still be mutable, and a link to each node will exist in its constructor, so it does not matter that not everything was configured until everything was configured. The following code compiles and, taking into account the pre-existing IEnumerable, creates 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 (almost all built-in collections do, and you can use OfType () to turn non-common ICollections and IEnumerables into common IEnumerables). The only thing to worry about is the call stack; there is a limit to the number of call calls you can nest, which can cause SOE in a finite but large list of entries.

EDIT: JaredPar raises a very good point; this solution uses Count () and Any (), which should take into account the results of Skip (), and therefore cannot use the "shortcuts" built into these methods, which can use the power property of the collection class. These calls become linear, which complicates the complexity of the algorithm. If you simply use the basic elements of IEnumerable, this becomes much more efficient:

 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 will lose a slightly more elegant error checking, but if IEnumerable is null, an exception will still be thrown.

Answer 3

Yes, you can create a link-setter object that is used to set the links that you send to the node constructor, or create a static create method that returns a link-setter. Links in node are private and can only be accessed through a "link-setter", and when you use them to configure the list, you throw them away.

However, this is a pretty useless exercise. If the list is immutable, it makes no sense to use a doubly linked list when a simple array works better.