Scala中的Java样式LinkedList

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

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

但是，考虑到Scala中存在空引用，尝试使用“null”终止创建具有“null”终止的java样式链表似乎非常难。

我尝试了以下内容

 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是一个带有可变成员的case类，对我来说似乎很不对。 但由于我必须在每次操作之前区分Empty和LinkedList，我需要模式匹配的帮助。

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

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

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

Answer 1

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

不，你不应该这样做。 向Node添加方法，并在Empty和LinkedList以不同方式实现它们。 当您需要模式匹配时，您可以：

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

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

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

作为一个起点：

 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中那样的双重链接列表。）