Reading time:

2 minutes

Word count:

323

Hello Everyone

Here is a Scala application example that demonstrate how to reverse a singularly linked list.

/* Written by Peter Pilgrim 10th December 2010 */
package uk.co.xenonique.scalaexercises

import scala.collection.mutable.StringBuilder
import java.lang.System

abstract class LinkedList { }

case object EmptyLinked extends LinkedList

case class LinkedNode( var value: Int, var next:LinkedList ) extends LinkedList


/**
 * Example Scala program that demonstrates an algorithm to reverse a singularly linked list of elements.
 */

object NodeApp {

  def traverse( node: LinkedList ): String = {
    def _traverse( node: LinkedList, buf: StringBuilder ): Unit = {
      node match {
        case b: LinkedNode => {
            buf.append( "%d, ".format( b.value ))
            _traverse( b.next, buf )
        }
        case _ =>
      }
    }

    val buf = new StringBuilder("[");
    _traverse( node, buf );
    buf.append("]")
    buf.toString
  }

  def reverse( current: LinkedList ): LinkedList = {
    def _reverse( current: LinkedList, parent: LinkedList ): LinkedList = {
      println("::>> current="+current+", parent="+parent)
      current match {
        case b: LinkedNode => {
           val revHead = _reverse( b.next, current )
           printf( "<<:: b.value=%d, b.next=0x%-8X, 
                  current=0x%-8X, parent=0x%-8X\n",
                  b.value, 
                  System.identityHashCode(b.next),
                  System.identityHashCode(current), 
                  System.identityHashCode(parent) )
           b.next = parent
           revHead
        }
        case _ => parent
      }
    }
    
    _reverse( current, null)
  }

  def main( args: Array[String]) {

    val s = LinkedNode( 1, 
               LinkedNode( 2, 
                LinkedNode(3, 
                  LinkedNode( 4, EmptyLinked ))))
    print("s="+traverse(s))
    val t = reverse(s)
    print("t="+traverse(t))

  }
}

The example program above demonstrates the following salient points:

• Scala’s syntax for use of case instance classes that reduce the boiler plate and add syntax sugar to ordinary object classes. (LinkedNode)
• One can declare case object class (EmptyNode)
• Case classes can extend other classes or traits or other case classes
• Scala’s ability to nest a function declaration inside another function declaration
• a recursive traversal algorithm to traverse a singularly linked node data structure
• a recursive algorithm to reverse the sequence of elements in the singularly linked node data structure

Merry Xmas