如何在 C# 中创建真正不可变的双向链表

本文关键字：不可变 双向链表 创建 | 更新日期: 2023-09-27 18:35:31

这更像是一个理论问题：在C#中是否有可能创建一个真正不可变的双链表？在我看来，一个问题是 2 个相邻节点的相互依赖关系。

我所说的"真正"是指使用只读字段。

如何在 C# 中创建真正不可变的双向链表

这可以通过棘手的构造函数逻辑来实现。 例如 

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

你激起了我的好奇心。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 都需要先实例化另一个节点。

然而，有不止一种方法可以剥这只猫的皮。如果列表的每个节点都从一个 ReadOnlyNode 的构造函数中递归实例化，该怎么办？在每个构造函数完成之前，每个级别的属性仍然是可变的，并且对每个 Node 的引用将存在于其构造函数中，因此在设置完所有内容之前，并非所有内容都已设置并不重要。下面的代码编译，并给定一个预先存在的 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（） 将非泛型 ICollections 和 IEnumerables 转换为泛型 IEnumerables）。唯一需要担心的是调用堆栈;可以嵌套的方法调用数量是有限制的，这可能会导致有限但较大的输入列表出现 SOE。

编辑：JaredPar提出了一个非常好的观点;这个解决方案使用Count（）和Any（），它们必须考虑Skip（）的结果，因此不能使用这些方法中内置的"快捷方式"，这些"快捷方式"可以使用集合类的基数属性。这些调用变为线性，这增加了算法的复杂性。如果您只使用 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 为空，则无论如何都会引发异常。

是的，您可以创建一个用于设置链接的"link-setter"对象，将其发送到节点的构造函数中，或者使用返回"link-setter"的静态创建方法。节点中的链接是私有的，只能通过"链接设置器"访问，当你使用它们来设置列表时，你会把它们扔掉。

然而，这是一个相当无用的练习。如果列表是不可变的，那么当一个简单的数组工作得更好时，使用双向链表是没有意义的。

相关文章：