PEAT Online Course -
How To Improve Your Personal Performance in Java work Technology

  • YOU + CONTROL
  • Focus
  • Autonomy
  • Proficiency
  • Purpose
  • Covid-19!!!
  • Deep Hidden Meaning
  • FREE updates
EARLY ACCESS (VIP)
Exclusively on
VIMEO ON-DEMAND

Scala: Reversing A Singularly Linked List

15 December 2010 Comments off

2 minutes

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

Hey all! Thanks for visiting. I provide fringe benefits to interested readers: checkout consultancy, training or mentorship Please make enquiries by email or
call +44 (0)7397 067 658.

Due to the Off-Payroll Working plan for the UK government, I am enforcing stricter measures on contracts. All potential public sector GOV.UK contracts engagements must be approved by QDOS and/or SJD Accounting. Please enquire for further information.