为什么Scala集合中没有不可变的双链表？

Question

看看这个问题,提问者对a中某个元素的第一个和最后一个实例感兴趣List,似乎更有效的解决方案是使用DoubleLinkedList可以从列表末尾向后搜索的问题.但是,集合API中只有一个实现,它是可变的.

为什么没有不可变版本？

Answer 1

因为每次要进行更改时都必须复制整个列表.使用普通链接列表,您至少可以在列表前添加,而无需复制所有内容.如果您确实希望在每次更改时复制所有内容,则不需要链接列表.您可以使用不可变数组.

Answer 2

这种结构存在许多障碍,但其中一个非常紧迫:双重链表不能持久.

这背后的逻辑非常简单:从列表中的任何节点,您都可以到达任何其他节点.因此,如果我将一个元素X添加到此列表DL,并尝试使用DL的一部分,我将面临这样的矛盾:从指向X的节点可以到达部分(DL)中的每个元素,但是,双链表的属性,即从部分(DL)的任何元素我可以到达指向X的节点.由于部分(DL)应该是不可变的并且是DL的一部分,并且因为DL不包括节点指向到X,那就是不可能.

非持久性不可变数据结构可能有一些用途,但它们通常对大多数操作都不好,因为每当生成衍生产品时都需要重新创建它们.

现在,创建相互引用严格对象的细微问题,但这是可以克服的.可以使用by-name参数和lazy val,或者像Scala的List一样:实际创建一个可变集合,然后将其"冻结"在不可变状态中(参见ListBuffer和它的toList方法).

Answer 3

因为在逻辑上不可能创建具有严格不变性的相互(循环)参照数据结构.

由于简单的存在顺序优先级,您无法创建两个相互指向的节点,因为创建另一个节点时,至少有一个节点不存在.

有可能通过涉及懒惰(通过变异实现)的技巧来获得这种循环,但真正的问题就变成了为什么你会首先想要这个东西？