Scala筆記 17 - List implementation探究

Scala list是如何implement的？ 以及他們的time complexity？

1. head

def head[T](list:List[T]) : T =
  list match {

    case Nil => throw new Error
    case x::xs => x
  }

head很簡單就直接return第一個element，是constant time


2. last

def last[T](list:List[T]): T = list match {

  case Nil => throw new Error
  case x::Nil => x

  case x::xs =>last(xs)
}

這個worst case是linear time


3. init (把list中最後一個element去掉）

def init[T](list:List[T]): List[T] = list match {
  case Nil => throw new Error
  case x::Nil => Nil  

  case x::xs => x::init(xs)
}

這個也是linear time


4. concat

def concat[T](list1:List[T], list2:List[T]) : List[T] =
  list1 match {
    case Nil => list2
    case x::Nil => x::list2
    case x::xs => x::concat(xs, list2)
  }

這個time complexity proportional to list1的長度


5. reverse

這個要用到我們之前implement的concat (一開始我忘了有implement concat，所以也可以用last/init去兜）

def reverse[T](list:List[T]): List[T] = list match {
  case Nil => Nil
  case x::xs => concat(reverse(xs), List(x))
}

time complexity: concat是linearly proportional to n, 而我們需要走過所有的element，所以是n*n complexity

所以就用我一開始想到的last和init去兜的話，就會有linear time complexity:

def reverseLinear[T](list:List[T]): List[T] = list match {
  case Nil => Nil
  case x::xs => last(list) :: reverseLinear(init(list))
}

6.  removeAt

def removeAt[T](n:Int, list:List[T]) : List[T] = list match {
  case Nil => Nil  

  case x::xs => if (n == 0) xs else x::removeAt(n-1,xs)
}

time complexity: linear


7. flatten
這要用到nested match

def flatten(list: List[Any]): List[Any] = {
  list match {
    case Nil => Nil    case x :: xs => x match {
      case y::ys => concat(flatten(y::ys) , flatten(xs))
      case nonlist => nonlist :: flatten(xs)
    }
  }
}