Is it possible to write an immutable doubly linked list?

Question

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?

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.

Answer 1

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.

Simplified problem: circular two-element "list"

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

Output:

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.

---

Immutable double-linked list

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

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

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

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.