Scientific Programming II

Programming in Scala

Lists

Our first real test of Scala's power will be in designing a linked list, but in a functional style. This implementation will be vastly different from our implementation in Java, but understand that the differences arise from differing paradigms, not that any way is better than other.

Object-Oriented Lists

First, we can look at re-implementing a linked list in Scala, using object-oriented practices. Scala is a hybrid language, so generally any Java construction is legal and easily translatable into Scala:

package edu.govschool.scala

/*
 * By default, Scala gives us one constructor for every class we write.
 * Everything in the class body that is NOT a method will be part of the
 * default constructor. We can provide arguments to that constructor by
 * providing the parameter list after the name of the class.
 * 
 * By default all properties will be private values. If we need any of them
 * to be mutable, we can define them using 'var'. If we want to access them
 * outside of the class, we will need to define getter/setter methods as
 * appropriate.
 */
class Node(data: Int, var next: Node) {
  /* If a function takes no parameters, we can leave off the parentheses.
   * If the return type can be inferred by the compiler (most of the time),
   * then we can also leave off the return type as well. Unless the IDE tells
   * you otherwise, leave off the return type.
   */
  def getData = data
  def getNext = next
  def setNext(node: Node) = next = node
  
  /*
   * Overridden functions MUST be declared as such, otherwise you will have
   * an error.
   */
  override def toString = "(" + data + ")"
}

object Node {
  def apply(data: Int, next: Node): Node = {
    new Node(data, next)
  }
}

class OOList {
  var head: Node = null
  var tail: Node = null
  
  def isEmpty = head == null
  
  def insertAtFront(data: Int): Unit = {
    if (head == null) {
      head = Node(data, null)
      tail = head
    } else {
      val tmp = Node(data, head)
      head = tmp
    }
  }

  def insertAtBack(num: Int): Unit = {
    if (isEmpty) {
      head = Node(num, null)
      tail = head
    } else {
      val tmp = tail
      tail = Node(num, null)
      tmp.setNext(tail)
    }
  }
  
  def removeFromFront = {
    if (isEmpty) println("Empty list")
    else head = head.getNext
  }
  def removeFromBack = {
    if (isEmpty) println("Empty list")
    else if (head == tail) {
      head = null
      tail = head
    } else {
      var prev = head
      var curr = head
      while (curr != tail) {
        prev = curr
        curr = curr.getNext
      }
      prev.setNext(null)
      tail = prev
    }
  }
  
  override def toString = {
    if (isEmpty) "Empty list"
    else {
      var tmp = head
      val sb = new StringBuilder()
      
      while (tmp != null) {
        sb.append(tmp)
        tmp = tmp.getNext
        
        if (tmp != null) {
          sb.append(" --> ")
        }
      }
      sb.append("\n").toString
    }
  }
}

object OOList {
  def apply() = new OOList()
}

object Main {
  def main(args: Array[String]) = {
    val l = OOList()
    
    l.insertAtBack(1)
    l.insertAtBack(2)
    l.insertAtBack(3)
    
    println(l)
  }
}