own implementation of Scalas List

listimpl.scala

package listimpl

import org.specs2.mutable.SpecificationWithJUnit
import org.specs2.specification.Scope

class LinkedListTest extends SpecificationWithJUnit {

  "LinkedList" should {
    "have  elements" in new Test {
      xs.size === 3
    }
    "have a string representation" in new Test {
      xs.toString === "LinkedList(1, 2, 3)"
      LNil.toString === "LNil"
    }
    "get an element by an idex" in new Test {
      (LNil(5): LinkedList[Int]) must throwA[IndexOutOfBoundsException]
      xs(-1) must throwA[IndexOutOfBoundsException]
      xs(3) must throwA[IndexOutOfBoundsException]
      xs(1) === 2
    }
    "reverse elements" in new Test {
      xs.reverse === LinkedList(3, 2, 1)
    }
    "prepend another LinkedList" in new Test {
      val ys = LinkedList(4, 5, 6)
      (xs ++: ys) === LinkedList(1, 2, 3, 4, 5, 6)
    }
    "append another LinkedList" in new Test {
      val ys = LinkedList(4, 5, 6)
      (xs ++ ys) === LinkedList(1, 2, 3, 4, 5, 6)
    }
    "do something for each element" in new Test {
      var ys = List[Int]()
      xs foreach { x => ys = x :: ys }
      ys === List(3, 2, 1)
    }
    "map the elements" in new Test {
      val ys = xs map { _+1 }
      ys === LinkedList(2, 3, 4)
    }
    "take the first elements" in new Test {
      (xs take 1) === LinkedList(1)
      (xs take 2) === LinkedList(1, 2)
      (xs take 3) === xs
      (xs take 4) === xs
    }
    "drop the first elements" in new Test {
      (xs drop 0) === xs
      (xs drop 1) === LinkedList(2, 3)
      (xs drop 2) === LinkedList(3)
      (xs drop 3) === LNil
    }
    "filter elements" in new Test {
      (xs filter { _%2 == 0 }) === LinkedList(2)
      (xs filter { _%2 != 0 }) === LinkedList(1, 3)
      (LinkedList[Int]() filter { _%2 == 0 }) === LNil
    }
    "contain an element" in new Test {
      (xs contains 2) === true
      (xs contains 5) === false
    }
    "find an element" in new Test {
      (xs find { _%2 == 0 }) === Some(2)
      (xs find { _%2 != 0 }) === Some(1)
    }
    "test if an element exists" in new Test {
      (xs exists { _%2 == 0}) === true
      (xs exists { _ > 5 }) === false
    }
    "fold left through the elements" in new Test {
      (xs.foldLeft(0) { _+_ }) === 6
      (0 /: xs) { _+_ } === 6
    }
    "sum all elements" in new Test {
      xs.sum === 6
    }
    "reduce left through the elements" in new Test {
      (xs reduceLeft { (ret, x) => ret+x }) === 6
    }
    "find min and max" in new Test {
      xs.min === 1
      xs.max === 3
    }
    "get init elements" in new Test {
      xs.init == List(1, 2)
    }
    "get last element" in new Test {
      xs.last === 3
    }
    "be sorted" in {
      val xs = LinkedList(6, 3, 5, 1, 2, 7, 9, 8, 4)
      xs.sorted === LinkedList((1 to 9): _*)
    } 
    "zip two LinkedLists" in new Test {
      (xs zip LinkedList(3, 2, 1)) === LinkedList(1 -> 3, 2 -> 2, 3 -> 1)
    }
  }
  
  trait Test extends Scope {
    val xs = LinkedList(1, 2, 3)
  }
}

//================================================================================

import scala.{ UnsupportedOperationException => UOE }

abstract class LinkedList[+A] { self =>
  def head: A
  def tail: LinkedList[A]
  def init: LinkedList[A]
  def last: A
  def isEmpty: Boolean
  
  def size: Int = {
    def loop(xs: LinkedList[A], i: Int): Int =
      if (xs.isEmpty) i else loop(xs.tail, i+1)
    loop(this, 0)
  }
  
  def +: [B >: A](x: B): LinkedList[B] =
    new +:(x, this)
  
  def ++: [B >: A](xs: LinkedList[B]): LinkedList[B] =
    if (this.isEmpty) xs
    else if (xs.isEmpty) this
    else {
      var ys: LinkedList[B] = this
      for (x <- xs.reverse)
        ys +:= x
      ys
    }
  
  def ++ [B >: A](xs: LinkedList[B]): LinkedList[B] =
    if (this.isEmpty) xs
    else this ++: xs
    
  def /: [B] (init: B)(f: (B, A) => B): B = this.foldLeft(init)(f)
  
  def :\ [B] (init: B)(f: (A, B) => B): B = this.foldRight(init)(f)
    
  def apply(index: Int): A = {
    if (this.isEmpty || index < 0 || index >= this.size)
      throw new IndexOutOfBoundsException(index.toString)
    else {
      var i = 0
      var cur = this
      while (i < index) {
        cur = cur.tail
        i += 1
      }
      cur.head
    }
  }
  
  def foreach[B](f: A => B) {
    var cur = this
    while (!cur.isEmpty) {
      f(cur.head)
      cur = cur.tail
    }
  }
    
  def map[B](f: A => B): LinkedList[B] = {
    var xs: LinkedList[B] = LNil
    for (x <- this)
      xs +:= f(x)
    xs.reverse
  }
  
  def take(elems: Int): LinkedList[A] =
    if (elems <= 0) LNil
    else if (elems >= this.size) this
    else {
      var i = 0
      var xs: LinkedList[A] = LNil
      var ys = this
      while (i < elems) {
        xs +:= ys.head
        ys = ys.tail
        i += 1
      }
      xs.reverse
    }
  
  def drop(elems: Int): LinkedList[A] =
    if (elems <= 0) this
    else if (elems >= this.size) LNil
    else {
      var i = 0
      var cur = this
      while (i < elems) {
        cur = cur.tail
        i += 1
      }
      cur
    }
  
  def filter(f: A => Boolean): LinkedList[A] = {
    var xs: LinkedList[A] = LNil
    for (x <- this)
      if (f(x))
        xs +:= x
    xs.reverse
  }
  
  def reverse: LinkedList[A] = {
    var xs: LinkedList[A] = LNil
    for(x <- this)
      xs +:= x
    xs
  }
  
  def contains[B >: A](elem: B): Boolean = {
    var xs = this
    for (x <- this)
      if (x == elem)
        return true
    false
  }
  
  def find(f: A => Boolean): Option[A] = {
    var xs = this
    for (x <- this)
      if (f(x))
        return Some(x)
    None
  }
  
  def exists(f: A => Boolean): Boolean =
    find(f) != None
  
  def foldLeft[B](init: B)(f: (B, A) => B): B =
    if (this.isEmpty) throw new UOE("nil.foldLeft")
    else {
      var ret = init
      for (x <- this)
        ret = f(ret, x)
      ret
    }
  
  def foldRight[B](init: B)(f: (A, B) => B): B =
    this.reverse.foldLeft(init) { (a, b) => f(b, a) }
  
  def reduceLeft[B >: A](f: (B, A) => B): B =
    if (this.isEmpty) throw new UOE("nil.reduceLeft")
    else this.tail.foldLeft[B](head) { f }
  
  def sum[B >: A](implicit num: Numeric[B]): B =
    (num.zero /: this) { num.plus }
  
  def max[B >: A](implicit ord: Ordering[B]): B =
    if (this.isEmpty) throw new UOE("nil.max")
    else this reduceLeft { (ret, x) => if (ord.gteq(ret, x)) ret else x }
    
  def min[B >: A](implicit ord: Ordering[B]): B =
    if (this.isEmpty) throw new UOE("nil.max")
    else this reduceLeft { (ret, x) => if (ord.lteq(ret, x)) ret else x }
  
  def mkString: String
  
  def mkString(start: String, sep: String, end: String): String = {
    val sb = StringBuilder.newBuilder
    sb append start
    sb append head
    
    if (!tail.isEmpty) {
      sb append sep
      sb append tail.head
      
      for (x <- tail.tail) {
        sb append sep
        sb append x
      }
    }
    sb append end
    sb.toString
  }
  
  def sorted[B >: A](implicit ord: Ordering[B]): LinkedList[B] = {
    import ord._
    def qsort(xs: LinkedList[B]): LinkedList[B] = {
      xs match {
        case LNil => LNil
        case x +: xs => qsort(xs filter { _ < x }) ++: LinkedList(x) ++: qsort(xs filter { _ >= x })
      }
    }
    qsort(this)
  }
  
  def zip[B](xs: LinkedList[B]): LinkedList[(A, B)] = {
    var ys: LinkedList[(A, B)] = LNil
    var i1 = this.iterator
    var i2 = xs.iterator
    while (i1.hasNext && i2.hasNext)
      ys +:= i1.next() -> i2.next()
    ys.reverse
  }
  
  def iterator: Iterator[A] = new Iterator[A] {
    var xs = self
    
    def next(): A = {
      val x = xs.head
      xs = xs.tail
      x
    }
    
    def hasNext = !xs.isEmpty
  }
}

object LinkedList {
  def apply[A](a: A*): LinkedList[A] =
    (a :\ empty[A]) { _ +: _ }
  def empty[A]: LinkedList[A] = LNil
}

private case class +: [A](head: A, tail: LinkedList[A]) extends LinkedList[A] {
  def init = this take this.size-1
  def last = (this drop this.size-1).head
  def isEmpty = false
    
  def mkString = mkString("LinkedList(", ", ", ")")
  
  override def toString = mkString
}

final case object LNil extends LinkedList[Nothing] {
  def head = throw new UOE("nil head")
  def tail = throw new UOE("nil tail")
  def init = throw new UOE("nil init")
  def last = throw new UOE("nil last")
  def isEmpty = true
    
  def mkString = ""
    
  override def toString = "LNil"
}

Don't give +: a mutable tail, it seem the only reason to do so is to make constructing it a left to right traversal of the A array in LinkedList.apply. You can avoid that by:

object LinkedList {
  def apply[A](a: A*): LinkedList[A] = a.foldRight(empty[A])((l, e) => new +:(l, e))
  def empty[A]: LinkedList[A] = LNil
}

Thanks for your response. I noticed this already. The problem with this solution is, that the Seq have to be reversed. I think that takes more time than appending to the last mutable element of the List. But mutable elements are not functional.

In method map, for example, I can change the behavior too:

def map[B](f: A => B): LinkedList[B] = {
  var xs: LinkedList[B] = LNil
  for (x <- this.reverse)
    xs = new +: (f(x), xs)
  xs
}

It's more functional but slower because of the reversing. Also, in method filter without mutable state I came only to this ugly solution:

def filter(f: A => Boolean): LinkedList[A] = {
  var xs = this
  var first: LinkedList[A] = LNil
  var last: +:[A] = null

  while (!xs.isEmpty) {
    if (f(xs.head)) {
      val cur = new +: (xs.head, LNil)
      if (first.isEmpty) first = cur
      else last.t = cur
      last = cur
    }
    xs = xs.tail
  }
  first
}

Maybe it is better, maybe not. Suggestions?

Oh, I'm sorry. I've copied the wrong version of filter. Here is the actual:

def filter(f: A => Boolean): LinkedList[A] = {
  var first: LinkedList[A] = LNil
  for (x <- this.reverse)
    if (f(x))
      first = new +: (x, first)
  first
}

This does not look ugly any more. Now, I think it is the better solution than the one with the mutable state.

I don't need full performance - this code is not for production. But it is shorter and easier to read.