An immutable dynamic linked list implementation, in scala.

DLLPlayground.scala

object DLLPlayground {

  trait DLList[+T] {

    def value: T
    def prev: DLList[T]
    def next: DLList[T]
    def isEmpty: Boolean

    def prepend[S >: T](element: S): DLList[S]
    def append[S >: T](element: S): DLList[S]

    def updatePrev[S >: T](newPrev: DLList[S]): DLList[S]
    def updateNext[S >: T](newNext: DLList[S]): DLList[S]

    def foreach(fn: T => Unit): Unit

    override def toString: String = value.toString
  }

  object Empty extends DLList[Nothing] {
    override def value: Nothing = throw new NoSuchElementException("value of empty list")
    override def prev: DLList[Nothing] = throw new NoSuchElementException("prev of empty list")
    override def next: DLList[Nothing] = throw new NoSuchElementException("next of empty list")
    override def isEmpty: Boolean = true

    override def prepend[S >: Nothing](element: S): DLList[S] = new DLCons[S](element, Empty, Empty)
    override def append[S >: Nothing](element: S): DLList[S] = new DLCons[S](element, Empty, Empty)

    override def updatePrev[S >: Nothing](newPrev: DLList[S]): DLList[S] = this
    override def updateNext[S >: Nothing](newNext: DLList[S]): DLList[S] = this

    override def foreach(fn: Nothing => Unit): Unit = ()
  }

  class DLCons[+T](override val value: T, p: => DLList[T], n: => DLList[T]) extends DLList[T] {

    override lazy val prev = p
    override lazy val next = n

    override def isEmpty: Boolean = false

    override def prepend[S >: T](element: S): DLList[S] = {
      lazy val head = prev.prepend(element).updateNext(result)
      lazy val result: DLList[S] = new DLCons[S](value, head, next.updatePrev(result))
      head
    }

    override def append[S >: T](element: S): DLList[S] = {
      lazy val result: DLList[S] = new DLCons[S](value, prev.updateNext(result), next.append(element).updatePrev(result))
      result
    }

    override def updatePrev[S >: T](newPrev: DLList[S]): DLList[S] = {
      lazy val result: DLList[S] = new DLCons[S](value, newPrev, next.updatePrev(result))
      result
    }

    override def updateNext[S >: T](newNext: DLList[S]): DLList[S] = {
      lazy val result: DLList[S] = new DLCons[S](value, prev.updateNext(result), newNext)
      result
    }

    override def foreach(fn: T => Unit): Unit = {
      var trav: DLList[T] = this

      do {
        fn(trav.value)
        trav = trav.next
      } while (!trav.isEmpty)
    }
  }

  def main(args: Array[String]): Unit = {
    val list: DLList[Int] = Empty.prepend(95).prepend(82).append(2).append(3).prepend(5).prepend(18).append(25)

    list.foreach(println)
  }
}