Scala中的Java样式LinkedList [英] Java style LinkedList in Scala

问题描述

尝试在Scala中实现LinkedList。我很乐意在scala中创建一个不可变的List作为ADT，如下所示。

Trying to implement a LinkedList in Scala. I'm quite comfortable with creating an immutable List as an ADT in scala like the following.

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]

但是在Scala中尝试创建一个带有null终止的java样式链表似乎很难，因为Scala中有一个空引用。

But trying to create a java style linkedlist with "null" termination seems very hard in scala, given there is a null reference in Scala.

我尝试了以下

sealed trait Node[+A] 
case object Empty extends Node[Nothing]
case class LinkedList[A](var head: A,var tail: Node[A]) extends Node[A]

LinkedList是一个带有可变成员的案例类，对我来说似乎非常错误。但由于我必须在每次操作之前区分Empty和LinkedList，我需要模式匹配的帮助。

LinkedList is a case class with mutable members, seems very wrong to me. But since I would have to differentiate between Empty and LinkedList before every operation, i need the help of pattern matching.

这是正确的方法吗？或者有更好的方法吗？

Is this the right way to do it? or is there an better way to do it?

同样在第二个例子中，我无法拥有像这样的共变体类型

Also in the second example i'm not able to have a co-variant type like this

case class LinkedList[+A](var head: A,var tail: Node[A]) extends Node[A]

推荐答案

但由于我必须在每次操作之前区分Empty和LinkedList，我需要帮助模式匹配。

But since I would have to differentiate between Empty and LinkedList before every operation, i need the help of pattern matching.

不，你不应该这样做。将方法添加到 Node 并在空和 LinkedList 相反。当你需要模式匹配时，你可以：

No, you shouldn't have to do that. Add methods to Node and implement them differently in Empty and LinkedList instead. When you do need to pattern match, you can:

val x: Node[A] = ...
x match {
  case Empty => ...
  case nonEmpty: LinkedList[A] => ... // use nonEmpty

不进行 LinkedList的原因案例类只是它自动允许对链表无意义的操作。

The reason not to make LinkedList a case class is just that it automatically allows operations which make no sense for linked lists.

此外，您当前的定义不允许创建一个空列表，然后向其添加一个元素（而不是创建一个新列表）。对于可变链表，列表不能 节点;它应将引用到节点。

In addition, your current definition doesn't allow to create an empty list and then add an element to it (as opposed to creating a new list). For mutable linked lists, a list can't be a node; it should refer to nodes instead.

作为起点：

object LinkedList {
  private sealed trait MaybeNode[A] // can't be covariant!
  private case class Empty[A]() extends MaybeNode[A]
  private class Node[A](var value: A, var next: MaybeNode[A])
}
class LinkedList[A] {
  private var first: MaybeNode[A] = Empty()
  def add(x: A): Unit = ???
  def length: Int = ???
  // any other methods you want to support
}

（这是一个单链表，而不是像Java那样的双链表。）

(This is a singly-linked list, not a doubly-linked one like in Java.)

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