今天要來介紹List

List是Scala裡常見的一種資料結構，它在Collections底下的層級關係長這樣

屬於Scala.collection.immutable
從上面的圖可以看出，List被歸類在Linear sequences這邊。Linearseq指的是這個collection可以被分為head和tail組件，並且可以操作它的head,tail和isEmpty方法。
另外一點是，Scala的List不像是Java的List(e.g. ArrayList)，Scala List是immutable，所以它的大小跟元素不能被改變。

要如何創建一個List?

Nil指的是空的List，::用法是將元素加到List前端。

val xs = List(1, 2, 3)    //List(1, 2, 3)
val xs = 1 :: 2 :: 3 :: Nil    //List(1, 2, 3)

val a = List(3)
val b = 2 :: a    //List(2, 3)
val c = 1 :: b    //List(1, 2, 3) 

以上是創建一個List的方式

List type

List的每個元素都有相同的type，假設一個List的type是String，寫成List[String]。
我們也可以讓complier來幫我們設定List type

有一種List type叫做Nothing，即List[Nothing]。
Nothing在這裡就相當於整個層級關係裡的"bottom type"，也就是說它是所有其他type的subtype。

List operation

• head 回傳List的第一個元素
• tail 回傳List中除了第一個元素以外的所有元素
• isEmpty 如果是empty List則回傳true

以下是Scala應用了List operation的插入排序法，各位可以停下來思考一下

def isort(xs: List[Int]): List[Int] =
    if xs.isEmpty then Nil
    else insert(xs.head, isort(xs.tail))

def insert(x: Int, xs: List[Int]): List[Int] =
    if xs.isEmpty || x <= xs.head then x :: xs
    else xs.head :: insert(x, xs.tail)

今天就先介紹到這邊