Singly linked list implementation in Scala
A list is just a wrapper for an element that also contains a pointer to another list, thus its definition is straightforward:

scala&gt; abstract class MyList[+A]
defined class MyList

scala&gt; case class MyCons[A](head: A, tail: MyList[A]) extends MyList[A]
defined class MyCons

scala&gt; case object MyNil extends MyList[Nothing]
defined object MyNil

scala&gt; val xs = MyCons(1, MyCons(2, MyCons(3, MyNil)))
xs: MyList[Int] = MyCons(1,MyCons(2,MyCons(3,MyNil)))

scala&gt; xs.head
res2: Int = 1

scala&gt; xs.tail
res3: MyList[Int] = MyCons(2,MyCons(3,MyNil))


This list is completely immutable. Because of the polymorphic type A it can take any type of element and because it is covariant +A, it can also take the subtypes of an element:

scala&gt; trait T
defined trait T

scala&gt; class X extends T
defined class X

scala&gt; val xs: MyList[T] = MyCons(new X, MyNil)
xs: MyList[T] = MyCons(X@56a13ea6,MyNil)


The covariant nature of type A also allows the definition of MyNil, which would not be possible otherwise because it is parameterized with type Nothing, Scalas bottom type.

This single linked list definition is also the actual implementation of type List in the stdlib of Scala, although this implementation contains some more optimization details and MyCons is called ::.

If you also want to access the members head and tail when you only have type MyList instead of the more concrete type MyCons then you have to declare them directly in the supertype:

abstract class MyList[+A] {
  def head: A
  def tail: MyList[A]
}

case class MyCons[A](head: A, tail: MyList[A]) extends MyList[A]

case object MyNil extends MyList[Nothing] {
  def head = throw new NoSuchElementException("MyNil.head")
  def tail = throw new NoSuchElementException("MyNil.tail")
}