Singly linked list implementation in Scala

Question

What could be a better implementation, following the Scala way of doing it?

class Node(itemValue: Object, nextItem:Node){
 val value = itemValue
 val next = nextItem
}
class MyList() {
 var start: Node =null
 def add(value:Object){
 val cache = start
 this.start = new Node(value,cache)
 }
 def print:Unit = {
 var n = start;
 println(n.value)
 while(n != null){
 println(n.value)
 n = n.next;
 }
 }
}

Answer 1

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

scala> abstract class MyList[+A]
defined class MyList
scala> case class MyCons[A](head: A, tail: MyList[A]) extends MyList[A]
defined class MyCons
scala> case object MyNil extends MyList[Nothing]
defined object MyNil
scala> val xs = MyCons(1, MyCons(2, MyCons(3, MyNil)))
xs: MyList[Int] = MyCons(1,MyCons(2,MyCons(3,MyNil)))
scala> xs.head
res2: Int = 1
scala> 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> trait T
defined trait T
scala> class X extends T
defined class X
scala> 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")
}

• sunilp: thanks for the wonderful explanation, but is it required to always have a immutable List implementation, what if i need to dynamically add close to millions of data in the list by parsing some text file? won't it would be good to have a mutable list which can have O(1) complexity for add
• kiritsuku: the prepend operation is O(1). And if you need to append, then you should use a different data structure. At least when you want to stay functional.
• Dilum Ranatunga: Prepends plus a destructive reverse at the end will get you pretty good performance, right?
• kiritsuku: @DilumRanatunga prepend+reverse is O(n). For a lot of cases that is not pretty good performance.
• Dilum Ranatunga: Agreed its a factor of two worse, but simply prepending to build the list is O(n) too.