LinkList remove duplicates using HashMap

LinkListRemoveDuplicateUsingHahsMap.scala

package linkedlist

import scala.annotation.tailrec
import scala.collection.immutable.HashMap


/**
  * LinkList remove duplicates using HashMap
  * Time Complexity O(n)
  * Space Complexity O(n) for hashmap if all are duplicates
  *
  */
object LinkListRemoveDuplicateUsingHahsMap extends App {

  /**
    * abstract Node
    */
  abstract class AbstractNode {
    def data: Int

    def next: AbstractNode
  }

  /**
    * Nil Node to indicate end of link list
    */
  object NilNode extends AbstractNode {
    def data = throw new NoSuchElementException("it is empty")

    override def toString() = s"Nil"

    def next = throw new UnsupportedOperationException("tail of empty list")
  }

  /**
    * Node class
    *
    * @param data
    * @param next
    */
  case class Node(data: Int, next: AbstractNode) extends AbstractNode {
    override def toString() = s"data: ${data} next: ${next}"
  }

  /**
    * add new node in the beginning
    *
    * @param head
    */
  implicit class NodeAdd(head: AbstractNode) {
    def prependItem(v: Int): AbstractNode = Node(v, head)
  }

  /**
    * remove duplicates using hashmap
    * Time Complexity O(n)
    * Space Complexity O(n) for hashmap if all are duplicates
    *
    * @param linkList
    * @return
    */
  def removeDup(linkList: AbstractNode) = {
    @tailrec
    def dup(next: AbstractNode, finalNodes: AbstractNode, map: HashMap[Int, Int]): AbstractNode = {
      next match {
        case NilNode => finalNodes
        case n =>
          if (map.exists(_._1 == n.data)) {
            dup(next.next, finalNodes, map)
          } else {
            dup(next.next, finalNodes.prependItem(n.data), map + (n.data -> n.data))
          }
      }
    }
    dup(linkList, NilNode, HashMap.empty[Int, Int])
  }

  val linkList =
    Node(1, NilNode)
      .prependItem(2)
      .prependItem(4)
      .prependItem(3)
      .prependItem(3)
      .prependItem(5)
      .prependItem(1)

  removeDup(linkList)
}