Scala中的LinkedList [英] LinkedList in Scala

问题描述

为了练习，我正在尝试在Scala中实现 LinkedList .

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

主要问题是有关 Null 引用.

但首先要输入一些代码:

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
}

在这一点上，我已经很担心了.我在构造中将 xnext 声明为 Option [Node] ，因为此 linkedList 中的尾部没有下一个.

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.

在我的第一次尝试中，它只是一个 Node ，但是存在null对象问题，因为编译器只是告诉我"null无法转换为Node"(或类似的东西，我确实现在不记得了)-所以我切换到此选项.

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.

但是，可以吗?因为，对我而言，下一个应该是 Node ，而不是 Option ，否则，我不知道 linkedList 中的方式引用下一个节点.

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.

我应该如何声明它们?节点?还是 Option [Node] ?
在 Add 方法中也存在问题.
添加节点时，我想添加一个 Node 对象，而不是一个 Option [Node] .
而且我不知道如何使用所有 Option ， Some 和 None 类来实现我想要的事情.

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.我已经阅读了此问题，但对我没有帮助

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

推荐答案

在这一点上，我已经很担心了.我在构造中将 xnext 声明为 Option[Node]，因为此链接列表中的尾部没有下一个.[...]但是，可以吗?因为，对于我来说，下一个应该是一个Node，而不是Option，否则，我不知道在linkedList中如何引用下一个Node.

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.

这是替换 null 的很好的解决方案，您肯定要这样做以防止null指针异常等. Option [Node] 只是包装在容器中的 Node (或 None ).您可以使用 isEmpty 检查它是否具有值或使用 get 获取其值(如果 Option 为空，则会引发异常).

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).

与 null 唯一的区别(如您在Java中使用的那样)是，您需要检查它是否 isEmpty 而不是检查null，并且您需要当您确定它不是 None 时，需要显式打开( option.get ).

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.

我应该如何嘲笑他们?节点?或Option [Node]?

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

如果存在变量没有值的可能性(即，如果在Java中有时将其设置为 null ，则使用 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).

添加节点时，我想添加一个Node对象，而不是Option [Node].

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

否，您想在内部添加 Option [Node] ，因为稍后需要检查是否设置了节点.与将事情设置为null相比，在Scala中，最好通过 Option [Node] .isEmpty 进行此操作.您已经在代码的某些部分(例如 addNode )中进行了此操作，在这里您进行了 Some(newNode)(我称其为将节点包装在一个选项"，但我不确定这是否是正确的术语.

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).

而且我不知道如何使用所有 Option、Some 和 None 类来实现我想要的东西.

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

您在 addNode 中所做的事情似乎在一定程度上是正确的，但是您以某种方式尝试在 else 中再次使用 null 分支.怎么样:

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)

这篇关于Scala中的LinkedList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！