5
\$\begingroup\$

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;
    }
  }


}
\$\endgroup\$
3
\$\begingroup\$

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")
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – sunilp Jan 8 '14 at 3:56
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – kiritsuku Jan 8 '14 at 8:11
  • \$\begingroup\$ Prepends plus a destructive reverse at the end will get you pretty good performance, right? \$\endgroup\$ – Dilum Ranatunga Jan 31 '14 at 7:04
  • \$\begingroup\$ @DilumRanatunga prepend+reverse is O(n). For a lot of cases that is not pretty good performance. \$\endgroup\$ – kiritsuku Jan 31 '14 at 14:03
  • \$\begingroup\$ Agreed its a factor of two worse, but simply prepending to build the list is O(n) too. \$\endgroup\$ – Dilum Ranatunga Jan 31 '14 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.