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
- A data structure that maintains state, like
LinkedList
, should keep its implementation, especially any var
s, private.
- There's really no need to have
Node
be a case class
or to define it outside of LinkedList
where it is used.
- An empty
LinkedList
has no head
so that should really be an Option
.
- 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 seek(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 = seek(node.get.next)//set next link
node //return this node
}
seek(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]