Write a sample implementation of generic linked list, which takes into account – Type Parameterization / traits and subclasses / covariant types, etc

trait Node[+T]{
  def isEmpty:Boolean
  def head:T
  def tail: Node[T]
  def prepend[U >:T] (value:U): Node[U] = new NonEmptyNode[U](value, this)
  def ::[U >:T] (value:U): Node[U] = prepend(value)
}
object Nil extends Node[Nothing] {
  def isEmpty:Boolean = true
  def head:Nothing = throw new UnsupportedOperationException("Node is empty")
  def tail: Nothing = throw new UnsupportedOperationException("Node is empty")
  override def toString: String = "."
}
class NonEmptyNode[T](val head:T, val tail: Node[T]) extends Node[T]{
  override def isEmpty:Boolean = false
  override def toString: String = s"${head} --> ${tail}"
}

 

Linked list above, can be used in following way

// Sample creation of two link list below
// Both will evaluate to - Node[Int] = 1 --> 2 --> 3 --> 4 --> .
val listOne = Nil prepend 4 prepend 3 prepend 2 prepend 1
val listTwo = 1::2::3::4::Nil

 

Reference

  1. Functional Programming Principles in Scala