Implementation of linked list in Scala

Question

Here is my implementation of a linked list in Scala.It is a very basic implementation to understand generics and use of Option in Scala. Please let me how I can make it better and implement it more effectively.

class LinkedList[A] {

  val element: A = element.asInstanceOf[A]
  var head: Node[A] = Node(this.element, None)

  def insert(newElement: A): Unit = {
    if (this.head.element == null) {
      this.head = Node(newElement, None)
    }

  }
  def insertafter(newElement: A, after: A): Unit = {
    var tempNode = find(after)
    var newNode = Node(newElement)
    newNode.next = tempNode.next
    tempNode.next = Some(newNode)


  }
  def remove(item:A): Unit = {

     var tempNode = findpreviousItem(item)
     tempNode.next = tempNode.next.get.next

  }
  def findpreviousItem(item:A) = {
     var currentNode = this.head
    while (!currentNode.next.get.element.equals(item) ) {

      currentNode = currentNode.next.get
    }
    currentNode
  }
  def find(item: A): Node[A] = {

    var currentNode = this.head
    while (!currentNode.element.equals(item) ) {

      currentNode = currentNode.next.get
    }
    currentNode

  }
  def display(): Unit = {

    var current = head
    println(current.element)
    while (current.next.getOrElse(None)!=None) {
      println(current.next.get.element)
      current = current.next.get

    }

  }
}
case class Node[A](element: A, var next: Option[Node[A]] = None)

Answer 1

Some of the coding and design decisions I find to be rather problematic. Here's a rundown of some issues and suggestions.

public interface / private implementation

1. A data structure that maintains state, like LinkedList, should keep its implementation, especially any vars, private.
2. There's really no need to have Node be a case class or to define it outside of LinkedList where it is used.
3. An empty LinkedList has no head so that should really be an Option.
4. The line val element: A = element.asInstanceOf[A] is unneeded. Type casting is almost always wrong (and in this case it doesn't do anything), and each Node maintains its own element so there's no need for LinkedList to keep a separate one.

I suggest:

private class Node(val element: A, var next: Option[Node])
private var head: Option[Node] = None

display()

It might make more sense to have display() return a String representation to the caller, who can then decide to inspect it, print it, save it, whatever.

Being that as it may, one line per Node element could start taking up lots of screen room. I thought this might be better.

def display(): Unit = {
  def loop(node: Option[Node]): Seq[String] =
    node.fold(Seq.empty[String])(n => n.element.toString +: loop(n.next))

  println(loop(head).mkString("[","->","]"))
}

insert()

Your code only inserts if the current LinkedList is empty, otherwise the insertion request is silently ignored. That doesn't seem very helpful. Wouldn't it make more sense if it inserts to the head of the LinkedList whether it is empty or not?

def insert(newElement: A): Unit =
  head = Some(new Node(newElement, head)) //move previous head to 2nd element

insertafter() and find()

The code inserts after finding the 1st element of the target value. What if you had a LinkedList of 5 -> 5 -> 5? It would be impossible to insert a 2 into the 3rd position: 5 -> 5 -> 2 -> 5

And what if the target value is not in the current LinkedList? Right now your code throws an exception. That should be avoided.

Let's address the 2nd problem by inserting at the end (appending) if the target value is not found. (I've moved the find() logic into the insertafter() method.)

def insertafter(newElement: A, after: A): Unit = {
  def find(node: Node): Unit =
    if (node.element.equals(after) || node.next.isEmpty) //found or ran out
      node.next = Some(new Node(newElement, node.next))  //insert here
    else
      find(node.next.get) //not found yet, go on to next

  head.fold(insert(newElement))(find) //if head is None, insert, else find
}

remove() and findpreviousItem()

These have similar issues. Here's my solution.

def remove(item:A): Unit = {
  def getNext(node: Option[Node]): Option[Node] =
    if (node.isEmpty) //couldn't find item
      node            //return this node
    else if (node.get.element.equals(item)) //found item
      node.get.next                         //return the forward link
    else {                                    //still looking
      node.get.next = getNext(node.get.next)  //set next link
      node                                    //return this node
    }
  head = getNext(head)
}

constructor

As it is, you can only create an empty LinkedList and then start inserting elements, one at a time, into it. It might be convenient to allow for the creation of a complete LinkedList all at once.

class LinkedList[A](initial: A*) {
  private class Node(val element: A, var next: Option[Node])
  private var head: Option[Node] = None
  initial.reverse.foreach(insert)
  . . . //etc.

Usage:

val ll = new LinkedList('x','y','z')  // [x->y->z]

Answer 2

Using Option I would most of the times avoid calling its .get method, unless I previously checked the option was defined (using .isDefined or .nonEmpty). I recommend you completely get rid of calls to .get and start with pattern matching only.

You also don't have a way to represent an empty list, that's an important flaw.

Here's a couple of things you should try (and fix) considering the above (assuming you can build linked lists using the following constructs which doesn't exist in your code):

• LinkedList("test").find("asd")
• LinkedList("test", "asd").remove("asd")
• LinkedList("test").remove("asdasd")