是否可以编写不可变的双链表?

Question

我觉得问这个有点愚蠢，但我目前正在学习函数式编程并完成了创建单向链表的练习，这让我思考，是否有可能创建一个不可变的双链表？

假设列表 A ：： B，在构造时，A 需要知道 B，但 B 也需要知道 A。 我一直在 Scala 中这样做，所以我不确定它是否特定于 Scala，但我无法想象它会如何工作。

我不是在找替代品，因为我不需要这个，我只是好奇。

Answer 1

是的，这是可能的。但是通常不会这样做，因为与单链表不同，双链表没有任何子结构，例如，当删除一个元素时，这些子结构可以重用。此外，这样的列表似乎并没有做任何不可变Vector无法做的事情。

尽管如此，让我们把它写下来，因为它很有趣。

简化问题：循环双元素"列表">

作为热身，请看一下简化的问题：一个循环的双元素"列表"，其中两个节点相互引用：

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
}
}

这确实有效，我们可以构建这个小的双节点数据结构，并在其上运行几百万次迭代：

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

循环演示的是：这是一个实际的数据结构，而不是一些奇怪的嵌套函数系列，这些函数在访问元素几次后会吹响堆栈。

---

不可变的双链表

我决定通过双链接连接的节点和两端的两个显式Nil元素来表示列表：

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部分大多无关紧要，我添加它只是为了以后可以检查和打印内容。有趣的问题是：我们如何实际实例化这样的列表？以下是将单个链表转换为双链表的一种方法：

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元素连接到列表的长尾，最后加入第一个Cons的LeftNil。

再次，一个小演示，一个"迭代器"，它不断在列表中来回运行数百万次迭代，偶尔打印当前元素：

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方法特别直观，如果不在一张纸上涂鸦几分钟，我就无法直接写下来。老实说，每次工作时我仍然有点惊讶。