LinkedList in Scala

问题:

For exercise I'm trying to implement a LinkedList in Scala.

Main problem is about Null reference.

But first some code:

class Node(xkey: String, xnext: Option[Node], xinfo: Int) {
  val key: String = xkey;
  var next = xnext.getOrElse(None);
  var info: Int = xinfo;

  def this(xkey: String, xinfo: Int) {
    this(xkey, None, xinfo);
  }

  def this(xkey: String) {
    this(xkey, None, -1);
  }

  @Override
  override def toString: String = key + ":" + info
}

At this point, I'm already concerned about things. I declare xnext in construct as a Option[Node], because the tail in this linkedList does not have a next.

In my first try, it was just a Node, but had problem with null object because compilator just told me that "null can't cast to Node" (or something like that, I do not remember now) - And so I switch to this Option.

But, is it ok? Because, you know, for me next should be a Node, not a Option, otherwise, I don't know, in the linkedList how to reference to next Node.

Whatever, second class (i.e. my Linked List)

class LinkedNode {

  private var first: Option[Node] = None;
  private var last: Option[Node] = None;

  def addNode(newNode: Node) = {
    if (first == null) {
      first = Some(newNode);
      last = Some(newNode);
      first.next = last;
    }
    else {
      last.next = newNode;
      newNode.next = null;
      last = newNode
    }
  }

  def size(): Long = {
    var currentNode : = first;
    var size = 0L;
    while (currentNode != null) {
      size+=1;
      currentNode = currentNode.next;
    }
    size
  }

  def findNodeByKey(key: String) : Node = {
    var currentNode = first;
    while(currentNode != null) {
      if (currentNode.key.equals(key))
        currentNode
      else {
        currentNode = currentNode.next;
      }
    }
    currentNode;
  }

  def delNodeByKey(key : String) : Boolean = {
    var currentNode = first;
    var previousNode = first;
    while(currentNode != null) {
      if (currentNode.key.equals(key)) {
        previousNode = currentNode.next;
        return true;
      }
      previousNode = currentNode;
      currentNode = currentNode.next;
    }
    return false;
  }


}

And nothing. I'm already block to my constructor because first and last.

How should I declare them? Node? Or Option[Node]?
Problems are also in Add method.
When I add a node, I want to add a Node object, not an Option[Node].
And I don't get how to achieve things I want with all Option, Some and None classes.

I know I should not be so vague with my request, but any help?

P.S. I've already read this Q/A and it didn't help me

回答1:

At this point, I'm already concerned about things. I declare xnext in construct as a Option[Node], because the tail in this linkedList does not have a next. [...] But, is ok? because, you know, for me next should be a Node, not a Option, otherwise, I don't know, in the linkedList how to reference to next Node.

This is a good solution to replacing null, which you definitely want to do to prevent null-pointer exceptions and the like. An Option[Node] is simply a Node wrapped in a container (or None). You can check whether or not it has a value with isEmpty or get its value with get (which will throw an exception if the Option is empty).

The only difference to null, as you'd use it in Java, is that you need to check if it isEmpty instead of checking for null, and that you need to unwrap (option.get) it explicitly when you're sure that it is not None.

A more paradigmatic (scala-typical) way of retrieving the value from an option is pattern matching:

option match {
    case Some(x) => println(x)
    case None => println("Whoops, no value :(")
}

Regarding your other questions, they are indeed a little vague.

How should I declere them? Node? or Option[Node]?

Use Option[Node] if the possibility exists that there's no value for the variable (i.e., if you'd set it to null sometimes in Java).

When I add a node, I want to add a Node object, not a Option[Node].

No, you want to add an Option[Node] internally, because you will need to check later on if a node is set or not. In Scala it is preferrable to do this via Option[Node].isEmpty compared to setting things to null. You're already doing this in some parts of your code (e.g., addNode), where you do Some(newNode) (I'd call this "wrapping the node in an Option", but I'm not entirely sure if that's the correct terminology).

And I don't get how to achieve things I want with all Option, Some and None class.

What you're doing in your addNode does seem correct to a degree, but you somehow try to use null again in the else branch. What about:

// We don't need Option[Node] for the parameter, because there 
// _must_ be a Node value to be added
def addNode(newNode: Node) = {
    if (first.isEmpty) {
        first = Some(newNode)
        last = Some(newNode)
        first.next = last
    } else {
        newNode.next = None
        last.next = Some(newNode)
        last = Some(newNode)
    }
}

(I didn't run that code, nor did I do an thorough check of your logic)