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")