LinkedMap.scala

package java2scala.homeworks

sealed trait LinkedMap[K, V] extends Traversable[(K, V)] {

  override def toString: String = if (this.isInstanceOf[LinkedMap.Empty[K, V]]) {
    s"(Empty)"
  } else {
    s"(Cons[${sKey.get},${sValue.get}],${sRest.get})"
  }

  def sKey: Option[K]
  def sValue: Option[V]
  def sRest: Option[LinkedMap[K, V]]

  /** должен вернуть `false` если коллекция содержит хотя бы один элемент */
  override def isEmpty: Boolean = this.isInstanceOf[LinkedMap.Empty[K, V]]

  /** должен вернуть `true` если коллекция содержит ключ `key` */
  def contains(key: K): Boolean = if (isEmpty) {
    false
  } else {
    this.sKey.get == key || sRest.get.contains(key)
  }

  /** возвращает Some со значением значения, если коллекция содержит ключ `key`
    * и None если не содержит */
  def apply(key: K): Option[V] = if (isEmpty) {
    None
  } else {
    if (this.sKey.get == key) sValue
    else sRest.get.apply(key)
  }

  /** возвращает новый LinkedMap[K, V],
    * в котором добавлено или изменено значение для ключа `key` на `value` */
  def update(key: K, value: V): LinkedMap[K, V] = {
    def updateIt(key: K, value: V, curr: LinkedMap[K, V]): LinkedMap[K, V] = if (curr.isEmpty) {
      curr
    } else {
      if (curr.sKey.get == key) {
        LinkedMap.Cons(key, value, updateIt(key, value, curr.sRest.get))
      } else {
        LinkedMap.Cons(curr.sKey.get, curr.sValue.get, updateIt(key, value, curr.sRest.get))
      }
    }

    if (contains(key)) {
      updateIt(key, value, this)
    } else {
      updateIt(key, value, LinkedMap.Cons(key, value, this))
    }
  }

  /** возвращает новый LinkedMap[K, V]
    * состоящий из тех же позиций, но в обратном порядке */
  def reverse: LinkedMap[K, V] = {

    def reverseIt(curr: LinkedMap[K, V], prev: LinkedMap[K, V]): LinkedMap[K, V] = {
      val r = if (curr == this) {
        LinkedMap.Cons(curr.sKey.get, curr.sValue.get, LinkedMap.Empty[K, V]())
      } else {
        LinkedMap.Cons(curr.sKey.get, curr.sValue.get, prev)
      }

      if (curr.sRest.get.isEmpty) {
        r
      } else {
        var n = reverseIt(curr.sRest.get, r)
        n
      }
    }

    reverseIt(this, this.sRest.get)
  }

  /** создаёт новый LinkedMap, состоящий из элементов `this` и `other`
    * если какой-то ключ встречается в обеих коллекциях,
    * может быть выбрано любое значение*/
  def ++(other: LinkedMap[K, V]): LinkedMap[K, V] = {
    def add(list: List[K], first: LinkedMap[K, V], second: LinkedMap[K, V]): LinkedMap[K, V] = {

      if (first.isEmpty) {

        if (second.isEmpty) {
          LinkedMap.Empty[K, V]()
        } else if (list.contains(second.sKey.get)) {
          add(list, second, LinkedMap.Empty[K, V]())
        } else {
          LinkedMap.Cons[K, V](second.sKey.get, second.sValue.get, add(second.sKey.get :: list, second.sRest.get, LinkedMap.Empty[K, V]()))
        }

      } else if (list.contains(first.sKey.get)) {
        LinkedMap.Cons[K, V](first.sKey.get, first.sValue.get, add(list, first.sRest.get, second))
      } else {
        LinkedMap.Cons[K, V](first.sKey.get, first.sValue.get, add(first.sKey.get :: list, first.sRest.get, second))
      }

    }

    add(Nil, this, other)
  }

  /** создаёт новый LinkedMap , где ко всем значениям применена заданная функция */
  def mapValues[W](f: V => W): LinkedMap[K, W] = if (isEmpty) {
    LinkedMap.Empty[K, W]()
  } else {
    LinkedMap.Cons[K, W](sKey.get, f.apply(sValue.get), if (sRest.isEmpty) {
      LinkedMap.Empty[K, W]()
    } else {
      sRest.get.mapValues(f)
    })
  }

  /** создаёт новый LinkedMap , где ко всем значениям применена заданная функция,
    * учитывающая ключ*/
  def mapWithKey[W](f: (K, V) => W): LinkedMap[K, W] = if (isEmpty) {
    LinkedMap.Empty[K, W]()
  } else {
    LinkedMap.Cons[K, W](sKey.get, f.apply(sKey.get, sValue.get), if (sRest.isEmpty) {
      LinkedMap.Empty[K, W]()
    } else {
      sRest.get.mapWithKey(f)
    })
  }

  /** конструирует новый LinkedMap, содеоржащий все записи текущего, кроме заданного ключа */
  def delete(key: K): LinkedMap[K, V] = if (isEmpty) {
    LinkedMap.Empty[K, V]()
  } else {
    if (sKey.get == key) {
      sRest.get.delete(key)
    } else {
      LinkedMap.Cons[K, V](sKey.get, sValue.get, sRest.get.delete(key))
    }
  }

  /** применяет действие `action` с побочным эффектом ко всем элементам коллекции */
  def foreach[U](action: ((K, V)) => U): Unit = if (!isEmpty) {
    action.apply(sKey.get, sValue.get)
    if (!sRest.get.isEmpty) {
      sRest.get.foreach(action)
    }
  }
}

object LinkedMap {

  private def applyProtected[K, V](list: List[K], kvs: (K, V)*): LinkedMap[K, V] = kvs.length match {
    case l if l > 0 => {
      if (list.contains(kvs(0)._1)) {
        LinkedMap.applyProtected(list, kvs.drop(1): _*)
      } else {
        Cons[K, V](kvs(0)._1, kvs(0)._2, LinkedMap.applyProtected(kvs(0)._1 :: list, kvs.drop(1): _*))
      }
    }
    case _ => Empty[K, V]()
  }

  /** конструирует новый `LinkedMap` на основании приведённых элементов
    * каждый ключ должен присутствовать в результате только один раз
    * если в исходных данныхх ключ встречается несколько раз, может быть
    * выбрано любое из значений
    */
  def apply[K, V](kvs: (K, V)*): LinkedMap[K, V] = {
    applyProtected(Nil, kvs: _*)
  }

  final case class Cons[K, V](k: K, v: V, r: LinkedMap[K, V]) extends LinkedMap[K, V] {
    override val sKey = Some(k)
    override val sValue = Some(v)
    override val sRest = Some(r)
  }

  final case class Empty[K, V]()                              extends LinkedMap[K, V] {
    override val sKey: Option[K] = None
    override val sValue: Option[V] = None
    override val sRest: Option[LinkedMap[K, V]] = None
  }


  def main(args: Array[String]): Unit = {
    val t1 = LinkedMap.apply[Int, String]((1, "test1"), (2, "test2"), (3, "test3"), (4, "test4"))
    val t2 = LinkedMap.apply[Int, String]((5, "test5"), (6, "test6"), (7, "test7"), (8, "test8"))

    val r1 = t1.reverse

    println(r1)

    println(t1 ++ t2)
  }

}

В скале принято вместо isInstanceOf[_] использовать паттерн матчинг

Избегайте использования метода .get у Option, так как в случае None он приведет к выбрасыванию исключения. Даже в случае, если вы "уверены", что там Some(_), используйте .getOrElse

Данный код:

  def apply(key: K): Option[V] = if (isEmpty) {
    None
  } else {
    if (this.sKey.get == key) sValue
    else sRest.get.apply(key)
  }

можно переписать, например, так:

  def apply(key: K): Option[V] = sKey match {
    case Some(x) if x == key => Some(x)
    case _ => sRest.flatMap(_.apply(key))
  }