Singly linked list in Scala

Question

I've written a basic implementation of a singly linked list in Scala. I would appreciate any feedback and improvements (especially the remove() method, I feel like it could be implemented better).

Node class

class Node[T](data: T, var next: Option[Node[T]] = None) {
  override def toString: String = data.toString
}

Singly linked list implementation:

class SinglyLinkedList[T](var head: Node[T], var size: Int = -1){
  if(size == -1) size = calculateSize

  private def calculateSize: Int = {
    @scala.annotation.tailrec
    def traverse(count: Int, curNode: Option[Node[T]]): Int = curNode match {
      case None => count
      case Some(node) => traverse(count + 1, node.next)
    }
    traverse(0, Some(head))
  }

  override def toString: String = {
    @scala.annotation.tailrec
    def traverse(sb: StringBuilder, curNode: Option[Node[T]]): String = curNode match {
      case None => sb.append("None").toString
      case Some(node) => traverse(sb append (node + " --> "), node.next)
    }
    traverse(new StringBuilder, Some(head))
  }

  def append(d: T): Unit = {
    @scala.annotation.tailrec
    def traverse(curNode: Option[Node[T]]): Unit = curNode.flatMap(_.next) match {
      case None => curNode foreach (_.next = Some(new Node[T](d)))
      case next => traverse(next)
    }
    traverse(Some(head))
    size += 1
  }

  def remove(index: Int): Unit = {
    @scala.annotation.tailrec
    def traverse(elementsRemaining: Int, prevNode: Option[Node[T]], curNode: Option[Node[T]]): Unit = (elementsRemaining, curNode) match {
      case (_, None) => throw new NoSuchElementException
      case (0, n) =>
        if(prevNode.isEmpty) head.next.foreach(head = _)
        else prevNode.foreach(_.next = n.flatMap(_.next))
      case (i, n) => traverse(i - 1, n, n.flatMap(_.next))
    }
    traverse(index, None, Some(head))
    size -= 1
  }
}

Answer 1

Deficiencies

1. What's this piecemeal approach to functional/imperative programming? It makes code difficult to understand. In a particular part of a program, try to stick to a particular paradigm (I can't believe I had to say that. Multiparadigm languages have come a long way!).

2. You seem to not have noticed the glory of import. The glorious import scala.annotation.tailrec at the start of SinglyLinkedList would make all the tail-recursion annotations in your methods to simply @tailrec.

3. Node[T] should ideally be a case class. That would give you proper, compiler-implemented equals, toString and hashCode methods, alongside having easy pattern matching support, and not requiring new to instantiate them. By the way, did you know that Some is a case class?

4. You seem to be using Option as a replacement for null. IMHO, it complicates your code. Just use null if you have to. You're implementing the singly-linked list in classic reference/pointer based way after all. Don't get me wrong here, using Option is definitely better than using null, but I think it overcomplicates your code.

5. Do take a look at cons lists. I guess that's what you actually want.

6. Finally, a reference based list is not idiomatic Scala. A cons list (as above) is. Try to use that, it's not too far from what you're currently doing (I do hope that you want to do it the functional programming way, as you have not stated otherwise). As this is already not idiomatic Scala, you could go the full imperative route with while loops and null, as Scala allows you to do so. Or you could go the functional route with full immutability and cons lists. The choice is yours, but in this case, I and most other Scala programmers would recommend you choose the latter option. But whatever you do, keep this Frankenstein's monster imperative/functional hybrid from most people.

Suggestions

1. For remove(Int):Int, an algorithm is to do it the normal, C (pointer-based way). Traverse the list maintaining references to 2 elements, the current element and it's previous element. At the element to be removed, set the next field of the previous reference to refer to the element following the current element. This would work far better with while loops than flatMap and forEach. Again, imperative and functional don't really mix well in the same part of the program.

2. Take a look here for a reasonable functional singly linked list in Scala.