Eliminating null usage in a Scala stack implementation

Question

I'm learning Scala and am making some Stack implementations as practice. I made this and there are some apparent issues.

class LinkedStack[T] extends Stack[T] {
  var current: Node = null
  var n: Int = 0

  private class Node(e: T, prev: Node) {
    val element: T = e
    var previous: Node = prev
  }

  override def pop(): T = {
    if (n == 0) {
      throw new NoSuchElementException
    }
    val popNode: Node = current
    current = current.previous
    popNode.previous = null
    n -= 1

    popNode.element
  }

  override def peek(): T = {
    if (n == 0) {
      throw new NoSuchElementException
    }

    current.element
  }

  override def push(element: T): Unit = {
    if (element == null) {
      throw new NullPointerException
    }
    val newNode: Node = new Node(element, current)
    current = newNode

    n += 1
  }

  override def size(): Int = {
    n
  }

  override def toString(): String = {
    val builder = new StringBuilder("Stack top [")
    var temp: Node = current

    if (n == 0) {
      builder.append("]")
      return builder.toString()
    }
    while (temp.previous != null) {
      builder.append(temp.element).append(", ")
      temp = temp.previous
    }

    builder.append(temp.element).append("]")

    builder.toString()
  }
}

The trait includes all of the elements except toString. My main problem is that I'm using null pretty liberally. I know this shouldn't be done at all in Scala, and the line

var current: Node = null

in the constructor generates a compile error. How should I implement a constructor to create an empty stack? What's the best substitution for null?

Edit: You may have noticed that the Node class should be rewritten as

private class Node(val element: T, var previous: Node) {}

I realized this after reading Rex Kerr's answer. I forgot that I was programming in Scala when I first wrote that.

mutable.Stack is based on ListBuffer with source github.com/scala/scala/blob/v2.10.4/src/library/scala/… in which "val empty: Stack[Nothing] = new Stack(Nil)". Immutable.Stack is based on List with source in github.com/scala/scala/blob/v2.10.4/src/library/scala/… and the issue is avoided essentially by using the Nil of the empty List as the empty Stack. Both are good references for Scala stack design. — user4322779
– user4322779, Commented Jul 12, 2015 at 21:47
@cchantep - The converse is more true. If you have immutability, null is an even bigger pain to deal with. You can avoid null easily enough mutably, though. — Rex Kerr
– Rex Kerr, Commented Jul 13, 2015 at 3:21

Rex Kerr · Accepted Answer · 2015-07-13 03:19:52Z

2

There's nothing terribly wrong with using null as part of the internals for your class as long as those nulls never leak out and the logic is straightforward enough so you can be sure of that.

But if you want to not use null for practice, you have two choices. One is to use a built-in alternative: instead of Node use Option[Node] and use None for null. Given that your list is invariant, this is the easier way.

Second, you can replace Node with a hierarchy like so:

trait Node
class Elt(val element: T, val previous: Node) extends Node {}
object End extends Node

And then you use End wherever you use null now, and match on the Node any time you need to walk or do something, e.g.

def peek = current match {
  case End => throw new NoSuchElementException
  case Elt(e, _) => e
}

Of course this means each list has to create an extra object (End), and there are various other drawbacks, most of which can be gotten around to some extent. But for an exercise in avoiding null, you can ignore those complications.

answered Jul 13, 2015 at 3:19

Rex Kerr

168k27 gold badges325 silver badges411 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Nader Ghanbari Over a year ago

Agreed that nothing is terribly wrong by using null internally but still I would make the fact - that a var might be null - explicit by using an Option , independent of the whole structure being mutable or immutable (a very very tiny memory and time overhead but a huge advantage of avoiding mistakes and such).

user3599828 Over a year ago

@RexKerr The first option would make pushing the first element problematic since node.previous cannot point to a none instance. Is there any way around that?

Rex Kerr Over a year ago

@user3599828 - You make node.previous hold Option[Node].

Manjitha Teshara · Accepted Answer · 2018-07-16 06:16:56Z

1

i'm also scala learning my stack implementation ,it;s simple i used scala mutable array buffer

object Stack{
var stack=scala.collection.mutable.ArrayBuffer[Int]()

def isEmpty():Boolean={
  if(stack.length==0) true
  else false
}

def push(input:Int):Unit={
  stack+=input
}

def size():Int={
  stack.length
}

 def pop():Int={
   stack.remove(stack.length-1)
 }

def peek()={
   stack(stack.length-1)
 }

}

answered Jul 16, 2018 at 6:16

Manjitha Teshara

6022 gold badges9 silver badges22 bronze badges

1 Comment

jwvh Over a year ago

ArrayBuffer is mutable. There is no reason to make stack a var as well.

Collectives™ on Stack Overflow

Eliminating null usage in a Scala stack implementation

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related