不可变（双）LinkedList的高效实现 [英] Efficient implementation of immutable (double) LinkedList
问题描述
阅读此问题后，不可变或不可变？，并阅读我以前的问题的答案不变性，我仍然对有效实现简单的LinkedList是不可改变的有点困惑。在数组方面似乎很简单 - 复制数组并返回基于该副本的新结构。
假设我们有一个普通类的Node：
class Node {
private Object value;
private Node next;
}
并且基于上述的LinkedList类允许用户添加，删除等现在，我们如何确保不变性？在我们插入一个元素时，我们应该递归地将所有引用复制到列表中吗？
我也很好奇不可变或不可变的？提到了在二进制树的帮助下导致log（n）时间和空间的优先级优化。另外，我读到在前面添加elem的地方也是0（1）。这很困惑我，好像我们不提供引用的副本，那么在现实中我们正在修改两个不同来源的相同的数据结构，这破坏了不变性...
$ b $你的任何一个答案可以在双重链接的列表上工作吗？我期待任何答复/指向任何其他问题/解决方案。感谢您的帮助。
假设我们有一个普通类的Node和类LinkedList基于上述允许用户添加，删除等。现在，我们如何确保不变性？
通过使对象的每个字段只读，并确保其中一个只读字段引用的每个对象也都是不可变的一个不变的对象。如果这些字段都是只读的，并且仅引用其他不可变数据，那么清楚的对象将是不可变的！
如果我们递归地复制所有当我们插入元素时，引用列表？
你可以。你在这里得到的区别是不可变和持久化之间的区别。不可变数据结构无法更改。持续的数据结构利用了数据结构是不可变的，以便重新使用其部分。
持久不变的链接列表特别容易：
抽象类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;
私有readonly ImmutableList尾部;
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永远不会改变。
您的任何答案也可以在双向链接列表中工作？
你当然可以轻松地做一个双重链接的列表，每次完整的整个数据结构的副本，但这将是愚蠢的;您也可以使用数组并复制整个数组。
使持久化双向链接列表是相当困难的，但有办法做到这一点。我会做的是从另一个方向来解决这个问题。而不是说我可以持续的双向列表吗？问自己我觉得有吸引力的双链表的属性是什么？列出这些属性，然后查看是否可以找到具有这些属性的持久性数据结构。
例如，如果您喜欢的属性是双链表可以从任一端廉价地扩展到两个列表中，并且两个列表可以廉价地并置在一起，然后你想要的持久结构是一个不可变的catenable deque ，而不是一个双向链表。我举个例子说明一个不可改变的不可接纳的德克：
将其扩展为作为一个练习留下了可接受的德克;我链接到手指树上的文件是一个很好的阅读。
更新：
根据上述，我们需要将前缀复制到插入点。通过不变性的逻辑，如果w从前缀中删除任何内容，我们会得到一个新的列表以及后缀...为什么只复制前缀，而不是后缀？
很好的考虑一个例子。如果我们有列表（10，20，30，40），我们要在位置2插入25，该怎么办？所以我们想要（10,20,25,30,40）。
我们可以重用哪些部分？我们手头的尾巴是（20,30,40），（30,40）和（40）。很明显，我们可以重新使用（30，40）。
绘图可能有帮助。我们有：
10 ----> 20 ----> 30 -----> 40 ----->空
我们想要
10 ----> 20 ----> 25 -----> 30 -----> 40 ----->空
所以让我们让
| 10 ----> 20 --------------> 30 -----> 40 ----->空
| /
| 10 ----> 20 ----> 25 - /
我们可以重复使用（30,40），因为这部分对于列表。
更新：
是否可以提供随机插入的代码还有删除？
这是一个递归解决方案：
ImmutableList InsertAt（int value，int position）
{
if（position< 0）
抛出新的异常（）;
else if（position == 0）
return this.Add（value）;
else
return tail.InsertAt（value，position-1）.Add（head）;
}
你知道为什么这样吗？ p>
现在，作为一个练习，写一个递归的DeleteAt。
现在，作为一个练习，写一个 -recursive InsertAt和DeleteAt。记住，您有一个不可变的链接列表，您可以使用，因此您可以在迭代解决方案中使用一个
Having read this question Immutable or not immutable? and reading answers to my previous questions on immutability, I am still a bit puzzled about efficient implementation of simple LinkedList that is immutable. In terms of array tha seems to be easy - copy the array and return new structure based on that copy.
Supposedly we have a general class of Node:
class Node{
private Object value;
private Node next;
}
And class LinkedList based on the above allowing the user to add, remove etc. Now, how would we ensure immutability? Should we recursively copy all the references to the list when we insert an element?
I am also curious about answers in Immutable or not immutable? that mention cerain optimization leading to log(n) time and space with a help of a binary tree. Also, I read somewhere that adding an elem to the front is 0(1) as well. This puzzles me greatly, as if we don't provide the copy of the references, then in reality we are modifying the same data structures in two different sources, which breaks immutability...
Would any of your answers alo work on doubly-linked lists? I look forward to any replies/pointers to any other questions/solution. Thanks in advance for your help.
Supposedly we have a general class of Node and class LinkedList based on the above allowing the user to add, remove etc. Now, how would we ensure immutability?
You ensure immutability by making every field of the object readonly, and ensuring that every object referred to by one of those readonly fields is also an immutable object. If the fields are all readonly and only refer to other immutable data, then clearly the object will be immutable!
Should we recursively copy all the references to the list when we insert an element?
You could. The distinction you are getting at here is the difference between immutable and persistent. An immutable data structure cannot be changed. A persistent data structure takes advantage of the fact that a data structure is immutable in order to re-use its parts.
A persistent immutable linked list is particularly easy:
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);
And there you go. Of course you would want to add better exception handling and more methods, like IEnumerable<int> methods. But there is a persistent immutable list. Every time you make a new list, you re-use the contents of an existing immutable list; list3 re-uses the contents of list2, which it can do safely because list2 is never going to change.
Would any of your answers also work on doubly-linked lists?
You can of course easily make a doubly-linked list that does a full copy of the entire data structure every time, but that would be dumb; you might as well just use an array and copy the entire array.
Making a persistent doubly-linked list is quite difficult but there are ways to do it. What I would do is approach the problem from the other direction. Rather than saying "can I make a persistent doubly-linked list?" ask yourself "what are the properties of a doubly-linked list that I find attractive?" List those properties and then see if you can come up with a persistent data structure that has those properties.
For example, if the property you like is that doubly-linked lists can be cheaply extended from either end, cheaply broken in half into two lists, and two lists can be cheaply concatenated together, then the persistent structure you want is an immutable catenable deque, not a doubly-linked list. I give an example of a immutable non-catenable deque here:
Extending it to be a catenable deque is left as an exercise; the paper I link to on finger trees is a good one to read.
UPDATE:
according to the above we need to copy prefix up to the insertion point. By logic of immutability, if w delete anything from the prefix, we get a new list as well as in the suffix... Why to copy only prefix then, and not suffix?
Well consider an example. What if we have the list (10, 20, 30, 40), and we want to insert 25 at position 2? So we want (10, 20, 25, 30, 40).
What parts can we reuse? The tails we have in hand are (20, 30, 40), (30, 40) and (40). Clearly we can re-use (30, 40).
Drawing a diagram might help. We have:
10 ----> 20 ----> 30 -----> 40 -----> Empty
and we want
10 ----> 20 ----> 25 -----> 30 -----> 40 -----> Empty
so let's make
| 10 ----> 20 --------------> 30 -----> 40 -----> Empty
| /
| 10 ----> 20 ----> 25 -/
We can re-use (30, 40) because that part is in common to both lists.
UPDATE:
Would it be possible to provide the code for random insertion and deletion as well?
Here's a recursive solution:
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);
}
Do you see why this works?
Now as an exercise, write a recursive DeleteAt.
Now, as an exercise, write a non-recursive InsertAt and DeleteAt. Remember, you have an immutable linked list at your disposal, so you can use one in your iterative solution!
这篇关于不可变（双）LinkedList的高效实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
