Linked List

List.scala

import java.util.NoSuchElementException

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
  def length: Int
  def atIndex(i: Int): T
  def add(i: T): List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
  def length: Int = 1 + tail.length
  def add(i: T): List[T] = new Cons(i, this)
  def atIndex(i: Int) = if(i == 0) head else tail.atIndex(i - 1)
  override def toString = head.toString + " -> " + tail.toString
}

class Nil[T] extends List[T] {
  def isEmpty = true
  def length = 0
  def add(i: T): List[T] = new Cons(i, this)
  def head = throw new NoSuchElementException("Nil.head")
  def tail = throw new NoSuchElementException("Nil.head")
  def atIndex(i: Int) = throw new IndexOutOfBoundsException
  override def toString = "Nil"
}