Question

这更是一个理论问题: C# 中的任何手段是否能建立一个真正永恒的双重关联列表? 我所看到的一个问题是两个相邻节点的相互依赖性。

使用只读字段。

Answer 1

这可能与复杂的构建逻辑有关。例如,

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

你让我好奇不已读独行节点的课简单到可以定义:

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

在双链接列表中, read only 仅读的问题在于,对于每个节点,你必须指定在构建器中的前节点和下节点,因此,如果这些节点从构建器之外重新传递,则它们必须已经存在。但是,当您调用构建器时, 节点M需要先有一个原有的N节点, 作为其“ 下一个” 节点, 但节点N需要 M 作为其“ 先前的” 节点才能构建。这就造成了“ 切和蛋” 的状态, N 和 M 都需要先对其它节点进行即时转换。

但是,有不止一种方法可以剥去这只猫的皮。如果列表的每个节点都是从一个Read OnlyNode的构造者内部即刻转过来的呢? 在每一个构建者完成之前,每个层次的属性仍然是可变的,每个节点的引用在其构建者中将存在,因此,在一切都建立起来之前,并非一切都已经建立起来。以下的代码编译,并给一个先前存在的IEEVC 将产生一个不可更改的双重关联列表:

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

您可以用任何能够执行 IEV 数的收藏集来使用它( 几乎所有的内置收藏都这样做, 您可以使用 OfType () 将非通用的集聚和 IEV 数转换为通用的 IEO 数 ) 。唯一需要担心的就是调用堆叠; 您可以使用多少方法来呼叫嵌套, 这可能会在有限但大的输入列表上导致 SOE 。

< 坚固 > EDIT: JaredPar 提出了一个非常好的点; 此解决方案使用 Count () 和 Any () 。计算时必须考虑到跳过 () 的结果, 因而不能使用这些方法中所含的“ 捷径 ”, 这些方法可以使用收藏类的主要属性。这些调用成为线性, 使算法的复杂度成正方形。如果您只使用IEnumber 的基本成员, 这就会变得更出色 :

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

有了这个解决方案,你就会失去一些更优雅的错误检查, 但如果IEO数是无效的, 一个例外反正也会被丢弃。

Answer 3

是的, 您可以制作一个用于设置链接的“ 链接改进器” 对象, 用于设置链接, 发送到节点的构建器中, 或者使用静态创建方法返回“ 链接改进器 ” 。节点中的链接是私有的, 只能通过“ 链接改进器” 访问。当您使用这些链接来设置列表时, 您会将其丢弃。

然而,这是一个相当毫无用处的练习。如果列表是不可改变的, 当简单的数组工作效果更好时使用双重链接列表是毫无意义的。

友情链接