Skip to main content
deleted 1 character in body
Source Link
jwvh
  • 1.5k
  • 8
  • 10
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
    }
  val _head = getNext(head)
}
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
    }
  val _ = getNext(head)
}
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)
}
improved the remove()
Source Link
jwvh
  • 1.5k
  • 8
  • 10
def remove(item:A): Unit = {
  def seekgetNext(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 = seekgetNext(node.get.next)  //set next link
      node                                    //return this node
    }
  seek(head)
val _ = getNext(head)
}
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)
  ()
}
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
    }
  val _ = getNext(head)
}
Source Link
jwvh
  • 1.5k
  • 8
  • 10

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