Java style LinkedList in Scala

Question

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]

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

I tried the following

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 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]

This sounds like a mental exercise, but just in case you didn't already know, scala's built-in List class is an immutable linked list, and is implemented very similarly to your ADT. — Dylan
– Dylan, Commented Oct 25, 2016 at 21:06
I know about the in-built List class. I'm preparing for an tech interview and therefore trying to manually implement various Data structures and their varied forms. — AbrahamDaniel
– AbrahamDaniel, Commented Oct 27, 2016 at 23:54

Alexey Romanov · Accepted Answer · 2016-10-26 14:07:55Z

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

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

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.

As a starting point:

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
}

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

Collectives™ on Stack Overflow

Java style LinkedList in Scala

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related