为什么 Scala 集合中没有不可变的双链表？
查看这个问题，提问者对List<中某个元素的第一个和最后一个实例感兴趣/code>，似乎更有效的解决方案是使用可以从列表末尾向后搜索的 DoubleLinkedList。然而，集合 API 中只有一种实现，并且它是可变的。
为什么没有不可变版本？
Looking at this question, where the questioner is interested in the first and last instances of some element in a List, it seems a more efficient solution would be to use a DoubleLinkedList that could search backwards from the end of the list. However there is only one implementation in the collections API and it's mutable.
Why is there no immutable version?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
因为每次您想要进行更改时都必须复制整个列表。使用普通的链接列表，您至少可以在列表前面添加内容，而不必复制所有内容。如果您确实想在每次更改时复制所有内容，则不需要为此使用链接列表。您可以只使用不可变数组。
Because you would have to copy the whole list each time you want to make a change. With a normal linked list, you can at least prepend to the list without having to copy everything. And if you do want to copy everything on every change, you don't need a linked list for that. You can just use an immutable array.
这种结构有很多障碍，但其中一个非常紧迫：双向链表无法持久化。
这背后的逻辑非常简单：从列表上的任何节点，您都可以到达任何其他节点。因此，如果我向此列表 DL 添加一个元素 X，并尝试使用 DL 的一部分，我将面临这样的矛盾：从指向 X 的节点可以到达部分（DL）中的每个元素，但是，通过双向链表的属性，这意味着从part(DL)的任何元素我都可以到达指向X的节点。因为part(DL)应该是不可变的并且是DL的一部分，并且因为DL不包括指向X的节点对于 X，那只是不能 是。
非持久不可变数据结构可能有一些用途，但它们通常对大多数操作来说都是不利的，因为每当生成衍生品时都需要重新创建它们。
现在，创建相互引用的严格对象是一个小问题，但这是可以克服的。可以使用按名称参数和惰性值，也可以像 Scala 的 List 那样：实际创建一个可变集合，然后将其“冻结”为不可变状态（请参阅 ListBuffer 及其 toList 方法）。
There are many impediments to such a structure, but one is very pressing: a doubly linked list cannot be persistent.
The logic behind this is pretty simple: from any node on the list, you can reach any other node. So, if I added an element X to this list DL, and tried to use a part of DL, I'd face this contradiction: from the node pointing to X one can reach every element in part(DL), but, by the properties of the doubly linked list, that means from any element of part(DL) I can reach the node pointing to X. Since part(DL) is supposed to be immutable and part of DL, and since DL did not include the node pointing to X, that just cannot be.
Non-persistent immutable data structures might have some uses, but they are generally bad for most operations, since they need to be recreated whenever a derivative is produced.
Now, there's the minor matter of creating mutually referencing strict objects, but this is surmountable. One can use by-name parameters and lazy vals, or one can do like Scala's List: actually create a mutable collection, and then "freeze" it in immutable state (see ListBuffer and it's toList method).
因为从逻辑上讲不可能创建具有严格不变性的相互（循环）引用数据结构。
由于简单的存在排序优先级，您无法创建两个彼此指向的节点，因为在创建另一个节点时，至少其中一个节点将不存在。
可以通过涉及惰性的技巧（通过突变实现）来获得这种循环性，但真正的问题是为什么你首先想要这个东西？
Because it is logically impossible to create a mutually (circular) referential data-structure with strict immutability.
You cannot create two nodes that point to each other due to simple existential ordering priority, in that at least one of the nodes will not exist when the other is created.
It is possible to get this circularity with tricks involving laziness (which is implemented with mutation), but the real question then becomes why you would want this thing in the first place?
正如其他人所指出的，双链表没有持久的实现。您将需要某种树来接近您想要的特征。
特别是，您可能需要查看手指树，它提供前面和后面的访问为 O(1)，前面和后面的分摊插入为 O(1)，其他地方的插入为 O(log n)。 （这与大多数其他常用的树相反，它们在任何地方都有 O(log n) 访问和插入。）
另请参阅：
As others have noted, there is no persistent implementation of a double-linked list. You will need some kind of tree to get close to the characteristics you want.
In particular, you may want to look at finger trees, which provide O(1) access to the front and back, amortized O(1) insertion to the front and back, and O(log n) insertion elsewhere. (That's in contrast to most other commonly-used trees which have O(log n) access and insertion everywhere.)
See also:
作为@KimStebel 答案的补充，我想添加：
如果您正在寻找适合促使您提出这个问题的数据结构，那么您可能会看看 Extreme聪明：Scala 中的函数式数据结构 作者：@DanielSpiewak。
As a supplemental to the answer of @KimStebel I like to add:
If you are searching for a data structure suitable for the question that motivated you to ask this question, then you might have a look at Extreme Cleverness: Functional Data Structures in Scala by @DanielSpiewak.