高效实现不可变(双)LinkedList

Question

读过这个问题是不可变的还是不可变的？并阅读我之前关于不变性的问题的答案,我仍然有点困惑有效实现简单的LinkedList是不可变的.在数组方面似乎很容易 - 复制数组并返回基于该副本的新结构.

据说我们有一个通用的Node类:

class Node{
    private Object value;
    private Node next;
}

并基于上面的类LinkedList允许用户添加,删除等.现在,我们如何确保不变性？我们在插入元素时是否应该递归地复制对列表的所有引用？

我也对Immutable或不可变的答案感到好奇吗？提到了在二叉树的帮助下导致log(n)时间和空间的cerain优化.另外,我在某处读到,在前面添加一个元素也是0(1).这让我很困惑,好像我们没有提供参考文献的副本,然后实际上我们正在修改两个不同来源的相同数据结构,这打破了不变性......

您的任何答案是否都适用于双向链接列表？我期待着对任何其他问题/解决方案的任何回复/指示.在此先感谢您的帮助.

Answer 1

据说我们有一个基于上面的Node和类LinkedList的通用类,允许用户添加,删除等等.现在,我们如何确保不变性？

通过使对象的每个字段只读,并确保其中一个只读字段引用的每个对象也是一个不可变对象,可以确保不变性.如果字段都是只读的并且只引用其他不可变数据,那么显然该对象将是不可变的!

我们在插入元素时是否应该递归地复制对列表的所有引用？

你可以.你在这里得到的区别是不可变和持久的区别.无法更改不可变数据结构.甲持久数据结构采用的一个事实,即一个数据结构是不可变的,以便重新使用它的部件的优势.

持久不可变链表特别容易:

abstract class ImmutableList
{
    public static readonly ImmutableList Empty = new EmptyList();
    private ImmutableList() {}
    public abstract int Head { get; }
    public abstract ImmutableList Tail { get; }
    public abstract bool IsEmpty { get; }
    public abstract ImmutableList Add(int head);
    private sealed class EmptyList : ImmutableList
    {
        public override int Head { get {  throw new Exception(); } }
        public override ImmutableList Tail { get { throw new Exception(); } }
        public override bool IsEmpty { get { return true; } }
        public override ImmutableList Add(int head)
        {
            return new List(head, this);
        }
    }

    private sealed class List : ImmutableList
    {
        private readonly int head;
        private readonly ImmutableList tail;
        public override int Head { get { return head; } }
        public override ImmutableList Tail { get { return tail; } }
        public override bool IsEmpty { get { return false; } }
        public override ImmutableList Add(int head)
        {
            return new List(head, this);
        }
    }
}
...
ImmutableList list1 = ImmutableList.Empty;
ImmutableList list2 = list1.Add(100);
ImmutableList list3 = list2.Add(400);

你去吧 当然,您可能希望添加更好的异常处理和更多方法,如IEnumerable<int>方法.但是有一个持久的不可变列表.每次创建新列表时,都会重用现有不可变列表的内容; list3重新使用list2的内容,它可以安全地执行,因为list2永远不会改变.

您的任何答案是否也适用于双向链接列表？

当然,您可以轻松地创建一个双向链表,每次都可以完整复制整个数据结构,但这样做会很愚蠢; 你不妨只使用一个数组并复制整个数组.

制作持久的双向链表非常困难,但有办法实现.我要做的是从另一个方向解决问题.而不是说"我可以制作一个持久的双向链表吗？" 问自己"我觉得有吸引力的双重链表的属性是什么？" 列出这些属性,然后查看是否可以提出具有这些属性的持久数据结构.

例如,如果您喜欢的属性是双向链接列表可以从任何一端廉价地扩展,便宜地分成两半到两个列表,并且两个列表可以廉价地连接在一起,那么您想要的持久性结构是不可变的可连接的双端队列,而不是双重链表.我在这里举一个不可变的非可连接双端队列的例子:

http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx

将它扩展为可以连接的双端队列是一种练习; 我在手指树上链接的纸是一个很好的阅读.

更新:

根据上面我们需要将前缀复制到插入点.通过不变性逻辑,如果w从前缀中删除任何内容,我们会得到一个新列表以及后缀...为什么只复制前缀,而不是后缀？

好吧考虑一个例子.如果我们有列表(10,20,30,40),我们想在第2位插入25怎么办？所以我们想要(10,20,25,30,40).

我们可以重用哪些部分？我们手头的尾巴是(20,30,40),(30,40)和(40).显然我们可以重复使用(30,40).

绘制图表可能会有所帮助.我们有:

10 ----> 20 ----> 30 -----> 40 -----> Empty

我们想要

10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty

让我们来吧

| 10 ----> 20 --------------> 30 -----> 40 -----> Empty
|                        /
| 10 ----> 20 ----> 25 -/ 

我们可以重复使用(30,40),因为该部分对两个列表都是共同的.

更新:

是否有可能提供随机插入和删除的代码？

这是一个递归解决方案:

ImmutableList InsertAt(int value, int position)
{
    if (position < 0) 
        throw new Exception();
    else if (position == 0) 
         return this.Add(value);
    else 
        return tail.InsertAt(value, position - 1).Add(head);
}

你知道为什么会这样吗？

现在作为练习,编写一个递归的DeleteAt.

现在,作为练习,编写一个非递归的 InsertAt和DeleteAt.请记住,您有一个不可变的链表可供使用,因此您可以在迭代解决方案中使用一个!