abstract class MyDoublyLinkedList[+A] {

  def head: A
  def previous: MyDoublyLinkedList[A]
  def tail: MyDoublyLinkedList[A]
  def isEmpty: Boolean

  def prepend[B >:A](element: B): MyDoublyLinkedList[B]

}

case object EmptyDoublyLinkedList extends MyDoublyLinkedList[Nothing] {

  override def head: Nothing = throw new NoSuchElementException("No Head for Empty")

  override def previous: MyDoublyLinkedList[Nothing] = throw new NoSuchElementException("No Previous for Empty")

  override def tail: MyDoublyLinkedList[Nothing] = throw new NoSuchElementException("No Next for Empty")

  override def isEmpty: Boolean = true

  override def prepend[B >: Nothing](element: B): MyDoublyLinkedList[B] =
    ConsDoublyLinkedList(element,this, this)
}


case class ConsDoublyLinkedList[+A](h: A, prev: MyDoublyLinkedList[A], t: MyDoublyLinkedList[A]) extends MyDoublyLinkedList[A]{
  override def head: A = h

  override def previous: MyDoublyLinkedList[A] = prev

  override def tail: MyDoublyLinkedList[A] = t

  override def isEmpty: Boolean = false

  override def prepend[B >: A](element: B): MyDoublyLinkedList[B] = {
    val newNode = ConsDoublyLinkedList(element, null, this)
    newNode
  }
}

object MyDoublyLinkedListTest extends App {

  val initialList = ConsDoublyLinkedList(1, EmptyDoublyLinkedList, EmptyDoublyLinkedList)
  println(initialList.prepend(100).prepend(200))
}