Scala immutable linked list with cycles

Question

In Scala, I need to make an immutable linked list with cycles. Something like:

case class Node(element: Int, next: Node)
val linkedList = Node(1, Node(2, null))
val cycle = Node(3, cycle)

cycle.next // this should go back to the same element

But it doesn't work. How do I make an immutable linked list with cycles?

Answer 1

Use lazy values and by-name parameters to defer initialization:

class Node(val element: Int, next_ : => Node) {
  lazy val next = next_
}

lazy val root: Node =
  new Node(1,
    new Node(2,
      new Node(3, root)
    )
  )

// tail-recursive print function as a bonus
def printRec(node: Node, depth: Int): Unit = if (depth > 0) {
  println(node.element)
  printRec(node.next, depth - 1)
}

printRec(root, 10)

Output:

1
2
3
1
2
3
1
2
3
1