读过这个问题不可变还是不可变？并阅读我之前关于不变性的问题的答案，我仍然对有效实现不可变的简单 LinkedList 感到有些困惑。就数组而言，这似乎很容易——复制数组并基于该副本返回新结构。
假设我们有一个通用的 Node 类：
class Node{
private Object value;
private Node next;
}
并且基于上面的类 LinkedList 允许用户添加、删除等。现在，我们将如何确保不变性？当我们插入一个元素时，我们是否应该递归地复制所有对列表的引用？
我也对不可变或不可变的答案感到好奇？提到在二叉树的帮助下导致 log(n) 时间和空间的 cerain 优化。另外，我在某处读到，在前面添加一个元素也是 0(1)。这让我非常困惑，好像我们不提供引用的副本，然后实际上我们正在修改两个不同来源中的相同数据结构，这破坏了不变性......
您的任何答案都适用于双向链表吗？我期待任何其他问题/解决方案的回复/指示。在此先感谢您的帮助。
假设我们有一个通用的 Node 类和基于上述的 LinkedList 类，允许用户添加、删除等。现在，我们如何确保不变性？
您可以通过将对象的每个字段设为只读来确保不变性，并确保这些只读字段之一引用的每个对象也是不可变对象。如果字段都是只读的并且只引用其他不可变数据，那么显然该对象将是不可变的！
当我们插入一个元素时，我们是否应该递归地复制所有对列表的引用？
你可以。您在这里得到的区别是immutable和persistent之间的区别。不可变的数据结构无法更改。持久数据结构利用数据结构不可变这一事实来重用其部分。
一个持久的不可变链表特别容易：
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 永远不会改变，所以它可以安全地做到这一点。
您的任何答案是否也适用于双向链表？
当然，您可以轻松地创建一个双向链表，每次都对整个数据结构进行完整复制，但这很愚蠢；您不妨只使用一个数组并复制整个数组。
制作一个持久的双向链表非常困难，但有一些方法可以做到。我要做的是从另一个方向解决问题。而不是说“我可以制作一个持久的双向链表吗？” 问问自己“我觉得双向链表有哪些吸引人的属性？” 列出这些属性，然后看看您是否可以提出具有这些属性的持久数据结构。
例如，如果你喜欢的属性是双向链表可以廉价地从两端扩展，廉价地分成两个列表，并且两个列表可以廉价地连接在一起，那么你想要的持久结构是一个不可变的可连接双端队列，而不是双向链表。我在这里举了一个不可变的不可连接双端队列的例子：
将其扩展为可连接的双端队列留作练习；我链接到的关于手指树的论文是一本很好读的论文。
更新：
根据上面我们需要将前缀复制到插入点。根据不变性的逻辑，如果 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。请记住，您有一个不可变的链表供您使用，因此您可以在迭代解决方案中使用它！
当我们插入一个元素时，我们是否应该递归地复制所有对列表的引用？
您应该递归地复制列表的前缀直到插入点，是的。
这意味着插入不可变链表是O(n)。（就像在数组中插入（而不是覆盖）一个元素一样）。
出于这个原因，插入通常是不受欢迎的（以及附加和连接）。
不可变链表的通常操作是“cons”，即在开头附加一个元素，即O(1)。
您可以清楚地看到例如 Haskell 实现的复杂性。给定一个定义为递归类型的链表：
data List a = Empty | Node a (List a)
我们可以直接将“cons”（在前面插入一个元素）定义为：
cons a xs = Node a xs
显然是O(1)操作。而插入必须递归地定义——通过找到插入点。将列表分解为前缀（复制），并与新节点和对（不可变）尾部的引用共享。
关于链表要记住的重要一点是：
对于不可变列表，这意味着：
如果您经常插入新元素，则首选基于日志的结构，例如树。
有一种方法可以模拟“突变”：使用不可变映射。
对于字符串的链表（Scala 风格的伪代码）：
case class ListItem(s:String, id:UUID, nextID: UUID)
然后ListItems可以将其存储在密钥为的地图中UUID：
type MyList = Map[UUID, ListItem]
如果我想插入一个新ListItem的val list : MyList：
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使用固定时间：http Map: //docs.scala-lang.org/overviews/collections/performance-characteristics
实现双链表也是类似的。