是否可以编写不可变的双向链表? [英] Is it possible to write an immutable doubly linked list?
问题描述
问这个问题我有点愚蠢，但是我现在正在学习函数编程，并完成了创建单链接列表的练习，这让我开始思考，甚至有可能创建一个不变的双链接列表吗?
I feel a little stupid for asking this, but I'm currently learning functional programming and completed an exercise on creating singly linked lists and it just got me thinking, is it even possible to create an immutable doubly linked list?
假设列表A :: B，在构造时，A需要了解B，但是B也需要了解A.我在Scala中一直在这样做，所以我不确定它是否特定到Scala，但我无法想象这将如何工作.
Suppose the list A :: B, at time of construction, A needs to know about B, but B also needs to know about A. I've been doing this in Scala, so I'm not sure if it's specific to Scala, but I can't picture how that would work.
我不是在寻找替代品，因为我什么都不需要，我只是很好奇.
I'm not looking for a substitute as I don't need this for anything, I'm just curious.
推荐答案
是的，有可能.但是通常不会这样做，因为与单链列表不同，双链列表不包含任何子结构，例如，当删除一个元素时，这些子结构可以重复使用.而且，这样的列表似乎没有做任何不变的 Vector 做不到的事情.
Yes, it's possible. It is usually not done though, because unlike a singly linked list, a double linked list does not have any substructures that could be reused when, for example, one element is removed. Moreover, such a list doesn't seem to do anything what an immutable Vector cannot do.
尽管如此，我们还是把它写下来，因为它很有趣.
Nevertheless, let's write it down, because it's fun.
简化的问题:圆形的两个元素的列表"
作为热身，看一下简化的问题:一个圆形的两个元素的列表"，其中两个节点相互引用:
As a warm-up, take a look at the simplified problem: a circular two-element "list" with two nodes referencing each other:
case class HalfRing(val value: Int)(otherHalf: => HalfRing) {
def next = otherHalf
}
object HalfRing {
def fullRing(a: Int, b: Int): HalfRing = {
lazy val ha: HalfRing = HalfRing(a){hb}
lazy val hb: HalfRing = HalfRing(b){ha}
ha
}
}
这确实可行，我们可以构建这个小的两节点数据结构，并在其上循环运行几百万次迭代:
This indeed works, and we can build this little two-node data structure, and run in circle on it for a few million iterations:
var r = HalfRing.fullRing(42, 58)
for (i <- 0 until 1000000) {
r = r.next
if (i % 100001 == 0) println(r.value)
}
输出:
58
42
58
42
58
42
58
42
58
42
循环演示的是:这是一个实际的数据结构，而不是一些奇怪的嵌套函数家族，它们在访问元素几次后会炸毁堆栈.
What the loop demonstrates is: this is an actual data structure, not some family of weirdly nested functions that blow the stack after accessing the elements a few times.
不可变的双向链接列表
我决定用与双链接相连的节点表示列表，并在两端使用两个显式的 Nil 元素:
I've decided to represent the list by nodes connected with double links, and two explicit Nil-elements at both ends:
sealed trait DLL[+A] extends (Int => A)
case class LeftNil[+A]()(n: => DLL[A]) extends DLL[A] {
def next = n
def apply(i: Int) = next(i)
}
case class RightNil[+A]()(p: => DLL[A]) extends DLL[A] {
def prev = p
def apply(i: Int) =
throw new IndexOutOfBoundsException("DLL accessed at " + i)
}
case class Cons[+A](value: A)(p: => DLL[A], n: => DLL[A]) extends DLL[A] {
def next = n
def prev = p
def apply(i: Int) = if (i == 0) value else next(i - 1)
}
apply 部分基本上无关紧要，我仅添加了它，以便以后可以检查和打印内容.有趣的问题是:我们实际上如何实例化这样的列表?这是一种将单个链表转换为双链表的方法:
The apply-part is mostly irrelevant, I added it only so I can inspect and print the content later. The interesting question is: how can we actually instantiate such a list? Here is a way to convert a single linked list into a double linked list:
object DLL {
def apply[A](sll: List[A]): DLL[A] = {
def build(rest: List[A]): (=> DLL[A]) => DLL[A] = rest match {
case Nil => RightNil[A]() _
case h :: t => {
l => {
lazy val r: DLL[A] = build(t){c}
lazy val c: DLL[A] = Cons(h)(l, r)
c
}
}
}
lazy val r: DLL[A] = build(sll){l}
lazy val l: DLL[A] = LeftNil(){r}
l
}
}
这里发生的事情基本上与上面的两个元素环相同，但是重复了多次.我们只是以连接两个半环的方式保持连接，不同的是，这里我们首先将小的 Cons 元素连接到列表的长尾，最后连接一个 LeftNil和第一个 Cons .
What happens here is essentially the same trick as with the two-element-ring above, but repeated multiple times. We just keep joining pieces in the same way we joined the two half-rings, except that here we are first joining small Cons-elements to long tails of a list, and finally join a LeftNil with the first Cons.
再次进行一个小演示，一个迭代器"，该迭代器在列表上来回运行数百万次迭代，并偶尔打印当前元素:
Again, a little demo, an "iterator" that keeps running on the list back and forth for a few millions iterations, and occasionally prints the current element:
val dll = DLL((42 to 100).toList)
println((1 to 20).map(dll))
@annotation.tailrec
def bounceBackAndForth(
dll: DLL[Int],
maxIters: Int,
direction: Int = +1
): Unit = {
if (maxIters <= 0) println("done")
else dll match {
case ln: LeftNil[Int] => bounceBackAndForth(ln.next, maxIters - 1, +1)
case rn: RightNil[Int] => bounceBackAndForth(rn.prev, maxIters - 1, -1)
case c: Cons[Int] => {
if (maxIters % 100003 == 0) println(c.value)
if (direction < 0) {
bounceBackAndForth(c.prev, maxIters - 1, -1)
} else {
bounceBackAndForth(c.next, maxIters - 1, +1)
}
}
}
}
bounceBackAndForth(dll, 1000000)
// cs_XIIIp4
备注:我发现递归的 build 方法不是特别直观，我无法直接写下来，而无需在纸上花点时间分钟.老实说，每次工作我都会感到有些惊讶.
Remark: I don't find the recursive build-method particularly intuitive, I couldn't write it down directly without scribbling on a piece of paper for a few minutes. To be honest, I'm still a bit surprised every time it works.
这篇关于是否可以编写不可变的双向链表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
