高效实现不可变(双)链表

Question

读过这个问题 不可变还是不可变？ 阅读我之前关于不变性的问题的答案，我仍然对不可变的简单 LinkedList 的有效实现感到有些困惑。就数组而言，这似乎很容易 - 复制数组并基于该副本返回新结构。

假设我们有一个通用的 Node 类：

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

和类 LinkedList 基于上述允许用户添加、删除等。现在，我们如何确保不变性？当我们插入一个元素时，我们是否应该递归复制对列表的所有引用？

我也很好奇不可变或不可变的答案？ 提到Cerain优化，在二叉树的帮助下导致log（n）时间和空间。另外，我在某处读到在前面添加一个挽歌也是 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 永远不会更改。

您的任何答案也适用于双向链表吗？

当然，您

可以轻松地制作一个双向链表，每次都执行整个数据结构的完整副本，但那将是愚蠢的;您不妨只使用数组并复制整个数组。

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

例如，如果您喜欢的属性是双向链表可以从两端廉价地扩展，廉价地分成两半，并且两个列表可以廉价地连接在一起，那么您想要的持久结构是不可变的可分类双端，而不是双向链表。我在这里举一个不可变的不可猫的 deque 的例子：

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。 请记住，您可以使用不可变的链表，因此您可以在迭代解决方案中使用一个链表！

Answer 2

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

您应该递归复制列表的前缀，直到插入点，是的。

这意味着插入到不可变链表中是 O（n）。（就像在数组中插入（不覆盖）元素一样）。

出于这个原因，插入通常是不受欢迎的（以及附加和串联）。

对不可变链表的通常操作是"cons"，即在开头附加一个元素，即 O（1）。

你可以清楚地看到Haskell实现的复杂性。给定一个定义为递归类型的链表：

data List a = Empty | Node a (List a)

我们可以直接将"cons"（在前面插入一个元素）定义为：

cons a xs = Node a xs

显然是 O（1） 操作。而插入必须递归定义 - 通过查找插入点。将列表分解为前缀（复制），并与新节点和对（不可变）尾部的引用共享该前缀。

关于链表，要记住的重要一点是：

• 线性访问

对于不可变列表，这意味着：

• 复制列表的前缀
• 分享尾巴。

如果您经常插入新元素，则首选基于日志的结构，例如树。

Answer 3

有一种方法可以模拟"突变"：使用不可变的映射。

对于字符串的链接列表（Scala 风格的伪代码）：

case class ListItem(s:String, id:UUID, nextID: UUID)

然后ListItems可以存储在UUID密钥的映射中： type MyList = Map[UUID, ListItem]

如果我想在val list : MyList中插入新ListItem：

def insertAfter(l:MyList, e:ListItem)={ 
     val beforeE=l.getElementBefore(e)
     val afterE=l.getElementAfter(e)
     val eToInsert=e.copy(nextID=afterE.nextID)
     val beforeE_new=beforeE.copy(nextID=e.nextID)
     val l_tmp=l.update(beforeE.id,beforeE_new)
     return l_tmp.add(eToInsert)
}

其中add、update、get使用Map http://docs.scala-lang.org/overviews/collections/performance-characteristics 需要恒定的时间：

实现双链表也是如此。