scala 实现链表

在学习数据结构时学到了链表，因为日常工作，写java写多了，想换个语言玩下，就试着想用scala实现一个链表。哪到知道碰到很多问题，
这里记录下使用scala时，所遇到的那些坑。

java链表

首先，我们先使用java来实现一个链表最简单的链表

public static class Node<T> { /** * 这里为了方便，就不用get和set方法那一套了 */ public Node next; public T data; } 

public static void main(String[] args) { Node<Integer> headNode = new Node<>(); headNode.data = 1; Node<Integer> secondNode = new Node<>(); secondNode.data = 2; headNode.next = secondNode; Node<Integer> thirdNode = new Node<>(); thirdNode.data = 3; secondNode.next = thirdNode; Node<Integer> fourthNode = new Node<>(); fourthNode.data = 4; thirdNode.next = fourthNode; Node<Integer> fifthNode = new Node<>(); fifthNode.data = 5; fourthNode.next = fifthNode; //遍历node Node<Integer> currentNode = headNode; while (currentNode != null) { System.out.println(currentNode.data); currentNode = currentNode.next; } } 

代码很简单，就不解释了，我们使用java实现了如下的数组。

同样的代码，我们使用scala实现一遍。

scala链表

case class Node[E](var next: Node[E], var data: E) { } def main(args: Array[String]): Unit = { val headNode = Node(null, 1) val secondNode = Node(null, 2) headNode.next = secondNode val thirdNode = Node(null, 3) secondNode.next = thirdNode val fourthNode = Node(null, 4) thirdNode.next = fourthNode val fifthNode = Node(null, 5) fourthNode.next = fifthNode var currentNode = headNode while (currentNode != null) { println(currentNode.data) currentNode = currentNode.next } } 

使用scala来实现链表也非常简单，除了预发以外基本上和java一模一样。

头部节点

好像从上面看，也没啥问题啊。考虑这样的情况，我们在实现一个链表时，经常会有一个设置一个不表示任何意义的头结点，以便于统一链表的操作（add和remove操作）

先来看看使用java如何创建这样一个“空节点”

public static class Node<T> { /** * 这里为了方便，就不用get和set方法那一套了 */ public Node next; public T data; } public static class List<T>{ private Node<T> headNode = new Node<>(); } public static void main(String[] args) { List<Integer> list = new List<>(); } 

没啥问题

同样的代码，看看scala

报了个错，Type mismatch, expected:E actual:Null ，scala的泛型不止是用于引用类型。

看这个图可以知道，null仅仅是AnyRef的子类，对于AnyVal这样的类型，比如Int，无法使用null赋值。

解决方法一:限制泛型的下界

即，限制泛型必须是Null的父类型

case class Node[E](var next: Node[E], var data: E) { } class List[E >: Null] { var headNode = new Node[E](null, null) } def main(args: Array[String]): Unit = { val l = new List[Integer] //问题，这里只能用Integer，无法使用Int了 } 

这种方式，解决了无法使用null赋值的问题。但是使用这种方式，必须使用new List[Integer] 无法使用基本类型比如 new List[Int]

解决方法二：todo