是否可以编写一个不可变的双向链表？

Question

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

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

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

Answer 1

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

不过还是写下来吧，因为很好玩

简化题：圆二元"list"

作为热身，看一下简化的问题：一个圆形的双元素 "list"，两个节点相互引用：

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

输出：

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

不可变双链表

我决定用双链接连接的节点和两端的两个显式 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 元素连接到列表的长尾，最后连接 LeftNil 与首先Cons。

再次，一个小演示，一个 "iterator" 使运行ning 在列表上来回数百万次迭代，并偶尔打印当前元素：

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-方法不是特别直观，没办法直接写下来不在纸上乱写几分钟。老实说，每次它的效果我还是有点惊讶。

是否可以编写一个不可变的双向链表？

Is it possible to write an immutable doubly linked list?

functional-programming

scala

immutability

immutable-collections