Question

1. List 是Scala 提供的列表，它是不可变对象，这与java.util.List 不同。

   List 的行为有些类似Java 的字符串：当你调用List 的某个方法，而这个方法的名字看起来像是会修改List 时，它实际上是创建并返回一个新的List 。

2. List 常用方法：

   • list1:::list2：拼接两个列表，返回新列表。

   • val2::list1：在list1 的头部添加一个新元素。

   • Nil：一个空列表对象。因此可以采用下面的方式初始化一个列表：

     
     xxxxxxxxxx
     val list = 1 :: 2 :: 3 :: Nil

   另外 List 也继承自 Traversable --> Iterable --> Seq --> LinearSeq，因此List 具有这些超类的所有方法。

3. 虽然 List 也提供了追加append 操作，记做:+，但该操作很少使用。因为向List 末尾追加元素的时间开销是 $ O(n) $ ， $ n $ 为列表大小。而使用:: 在列表头部添加元素只需要常量时间 $ O(1) $ 。

   如果希望通过追加的方式构建列表，则有两种方式：

   • 通过:: 依次在头部添加，最后通过.reverse() 方法来获取列表。
   • 采用ListBuffer ，它是一个可变列表，支持追加操作。构建完成后调用.toList() 方法即可。

4. 列表支持在头部快速添加、移除元素(复杂度 $ O(1) $ )，但是不支持快速访问下标（复杂的 $ O(n) $ )。这种特性意味着模式匹配很快。

7.1. 基本用法

1. List 字面量：

   
   xxxxxxxxxx
   val list = List(1,2,3,4)
   val list2 = List("a","b","c")

2. List列表 和 Array 很像，但是有两个重要区别：

   • 列表是不可变的，即：列表的内容一旦给定就无法改变。
   • 列表的结构是以链表的形式组织的，而 Array 的结构是一个数组。

3. 和 Array 一样，列表也是同构的：同一个列表的所有元素必须都是相同的类型。元素类型为 T 的列表的类型写作 List[T] 。

4. 列表类型是协变的。即：如果类型 S 是类型 T 的子类型，则 List[S] 是类型 List[T] 的子类型。

5. 空列表的类型为 List[Nothing]。由于 Nothing 是底类型，它是所有类型的子类。又由于 List 是协变的，因此对于任何 T 而言，List[Nothing] 是 List[T] 的子类型。

   这也是为什么我们可以写如下的代码：

   
   xxxxxxxxxx
   val list：List[String] = List() // List() 是 List[Nothing] 类型的对象

6. 所有的列表都构建自两个基本的构建单元：Nil 和 :: （读作 cons ）。

   Nil 表示空列表，中缀操作符 :: 表示在列表前面追加元素。即 x :: list 表示这样的列表：第一个元素为 x，接下来是列表 xs 的全部元素。

   因此列表也可以如下定义：

   
   xxxxxxxxxx
   val list = 1 :: ( 2 :: ( 3 :: ( 4 :: Nil ) ) )
   val empty = Nil

   事实上 List(...) 的定义最终展开成上述方式。

   由于以 :: 以冒号结尾，因此它是右结合的，因此前面的定义中可以去掉括号，得到：

   
   xxxxxxxxxx
   val list = 1 :: 2 :: 3 :: 4 :: Nil

7. 列表的基本操作：

   • list.head：返回列表的第一个元素。它只对非空列表有定义，对空列表调用时将抛出异常。
   • list.tail：返回列表的、除第一个元素之外的所有元素。它只对非空列表有定义，对空列表调用时将抛出异常。
   • list.isEmpty：返回列表是否为空。

   对列表的所有操作都可以用上述三个基础方法来表达。

8. 列表可以用模式匹配解开。列表模式可以逐一对应到列表表达式。

   既可以用List(...) 这样的模式匹配来匹配列表的所有元素，也可以用 :: 和 Nil 常量一点点的将列表解开。

   
   xxxxxxxxxx
   val list = List(1,2,3,4)
   val List(a,b,c,d) = list

   List(a,b,c,d) 模式匹配长度为 4 的列表，并将四个元素分别绑定到变量 a,b,c,d 。

   如果事先并不知道列表中元素的个数，或者列表中元素个数成千上万非常庞大，则更好的做法是使用 :: 来匹配。

   
   xxxxxxxxxx
   val a :: b :: rest = list

   这种模式匹配的是长度大于等于 2 的列表。其中 a 匹配第一个元素、b 匹配第二个元素、rest 匹配列表剩下的部分。

9. 事实上，List(...) 是一个由类库定义的提取器extractor 模式的实例。

   而 a :: b :: rest 作为模式时，p op q 这样的中缀操作等同于 op(p,q)，也就是中缀操作符 op 被当作构造方法模式处理的。具体而言，x :: xs 表达式相当于 :: (x,xs) 。

   一个细节是：存在名为 scala.:: 类，该类与 :: (x, xs) 模式构造方法相对应。因此 :: 在 scala 中出现两次：

   • 一次是作为 List 类的方法名，其作用是产出 scala.:: 类的实例。
   • 另一次是作为 scala 包中的一个类的名字。

10. 使用模式匹配是用基本方法 head,tail,isEmpty 来解开列表的变通方式。通常对列表做模式匹配要比用方法来解构更加清晰。

7.2 初阶用法

1. 如果一个方法不接收任何函数作为入参，则该方法被称作初阶方法。

2. ::: 操作符：拼接两个列表。

   
   xxxxxxxxxx
   list1 ::: list2

   和 :: 操作符类似，::: 操作符也是右结合的。即 xs ::: ys ::: zs 等价于 xs ::: (ys ::: zs) 。

3. .length 方法：获取列表长度。

   不同于数组，在列表上的 length 操作相对更耗资源。因为找到一个列表的末尾需要遍历整个列表，这需要消耗 $ O(n) $ 的时间。

   这也是为什么推荐使用 xs.isEmpty 测试，而不推荐使用 xs.length == 0 的原因。因为二者在结果上没有区别，但是后者的执行速度更慢，尤其当列表 xs 很长的时候。

4. .last 方法：获取（非空）列表的最后一个元素。

5. .init 方法：获取（非空）列表除了最后一个元素之外的剩余部分。

6. 和 .head 方法和 .tail 方法一样，.last / .init 这两个方法在应用到空列表上会抛出异常。

   不像 .head/.tail 那样在运行时消耗 $ O(1) $ 的常量时间，.last / .init 需要遍历整个列表来获取计算结果。因此它们的消耗时间复杂度为 $ O(n) $ 。

7. 最好将列表组织成：大量访问都集中在列表头部而不是尾部，从而获取更高的访问效率。

   如果需要频繁的访问列表的末尾，一个比较好的做法是：先将列表反转，然后变成了对反转后的列表的头部的访问。.reverse 方法就是反转列表，该方法会创建一个新的列表。

8. .drop 和 .take 方法是对 .tail 和 .init 的一般化，它们返回的是列表任意长度的前缀或后缀。

   • xs take n 返回列表 xs 的前 n 个元素；如果 n >= xs.length，则返回整个 xs 列表。
   • xs drop n 返回列表 xs 除了前 n 个元素的所有元素；如果 n >= xs.length，则返回空列表。

9. splitAt 方法将 列表从指定的下标位置切开，返回这两个列表组成的元组。该方法只需要遍历数组一次，而不是两次。

   
   xxxxxxxxxx
   List("a"，"b"，"c"，"d"，"e")。splitAt(2)// 返回结果 （List("a"，"b")，List("c"，"d"，"e"))

10. apply 用于从任意位置取元素，相对于数组而言，列表使用该方法比较少。它等价于 xs(n) 。

    
    xxxxxxxxxx
    xs.apply(2) // 选择 xs 的下标为 2 的元素

    该方法用的少的原因是 xs(n) 的时间复杂度为 $ O(n) $ 。

    事实上该方法是通过 drop 和 head 定义的：xs.apply(n) 等价于 (xs drop n).head 。

11. 列表的下标从 0 开始到列表长度减 1 ，和数组一样。.indices 方法返回了列表的所有有效下标的序列。

12. xs.flatten 方法将xs 扁平化，返回单个列表。其中 xs 是列表的列表。如果 xs 不满足条件，则编译错误。

13. xs.zip(ys) 方法返回一个由元组组成的列表。如果两个列表长度不同，则以最短的那个为主，没有配对上的元素被丢弃。

14. xs.zipwithIndex 方法返回一个元组组成的列表，元组的元素分别为原列表元素、该元素的下标。

    对该返回结果调用 .unzip 方法，则能够转换回列表组成的元组，第一个元素为原始列表 ，第二个元素为下标列表。

15. .toString 方法返回列表的标准字符串表现形式。

    
    xxxxxxxxxx
    List(1,2,3,4).toString // 返回 "List(1,2,3,4)"

    如果希望采用不同的表现形式，则可以使用 .mkString(pre，sep，post) 方法。该方法首先添加前缀字符串pre，然后添加每个元素并在元素之间添加分隔符 sep，最后添加后缀字符串 post 。

    
    xxxxxxxxxx
    List("1", "2", "3", "4").mkString("pre","#","post")// 返回 pre1#2#3#4post

    .mkString方法有两个重载的变种：

    • .mkString(sep)：它等价于 .mkString("",sep,"") 。
    • .mkString()：它等价于 .mkString("","","") 。

    .mkString 还有其它的变种，如 .addString，该方法并不是返回一个字符串，而是把构建出来的字符串追加到一个 StringBuilder 对象中。

    
    xxxxxxxxxx
    val buf = new StringBuilder
    List("a","b","c")。addString(buf,"pre",";","post")

    .mkString 和 .addString 这两个方法继承自 List 的超特质 Tranversable，因此它们也可以应用在所有其它集合类型上。

16. List 和 Array 的转换：

    • list.toArray 和 array.toList 方法

      
      xxxxxxxxxx
      val arr = "abcde".toArray // Array(a,b, c, d, e) ： Array[Char]
      arr.toList                //  List(a,b, c, d, e) ： List[Char]

    • list.copyToArray 方法可以将列表中的元素依次拷贝到目标数组的指定位置。

      
      xxxxxxxxxx
      val arr2 = new Array[Int](10)
      List(1,2,3)。copyToArray(arr2， 3)
      println(arr2.mkString(",")) // 0,0,0,1,2,3,0,0,0,0

17. 通过迭代器访问列表元素：list.iterator 方法。

    
    xxxxxxxxxx
    val it = List(1,2,3).iterator
    println(it.next) // 1
    println(it.next) // 2
    println(it.next) // 3
    println(it.next) // 抛出异常 ： java.util。NoSuchElementException

7.3 高阶方法

1. 高阶方法是接受函数为参数的方法。

2. 迭代方法：map 、 flatMap 、foreach ：

   • xs.map(f)：将类型为 List[T] 的列表 xs 的每个元素，通过函数 f: T => U 映射；再将映射结果拼接成列表返回。返回结果是 List[U] 类型的列表。

     
     xxxxxxxxxx
     List("this", "is", "a", "word").map(_.length) // 返回 ： List(4,2,1,4)

   • xs.flatMap(f)：和 map 类似，但是要求 f 返回一个列表 List[U]，然后将返回的所有列表的元素拼接成一个列表返回。返回结果是 List[U] 类型的列表。

     
     xxxxxxxxxx
     List("this","is").map(_.toList)// 返回 List(List(t, h, i, s),List(i,s))， 类型为 List[List[Char]]
     List("this","is").flatMap(_.toList)// 返回 List(t,h,i,s,i,s)， 类型为 List[Char]

   • foreach 方法：xs.foreach(f)，其中 f 返回结果为 Unit 。它简单的将 f 应用到列表中的每个元素，整个foreach 方法本身的结果类型也是 Unit 。

     
     xxxxxxxxxx
     var sum = 0
     List(1,2,3).foreach(sum += _)
     println(sum) // 6

3. 过滤方法：filter, partition, find, takeWhile, dropWhile, span：

   • xs.filter(f) 方法：将 f 应用到 xs的每个元素，保留 f(x) 为true 的元素。其中 函数 f 的类型为：f: T=> Boolean 。

     
     xxxxxxxxxx
     List(1,2,3,4).filter(_ %2 ==0)// 返回 List(2, 4)

   • xs.partition(f) 方法：和 .filter 方法类似，但是它返回一对列表：其中一个包含所有 f(x)=true 的元素，另一个包含所有 f(x)=false 的元素。

     
     xxxxxxxxxx
     List(1,2,3,4).partition(_ %2 ==0) // 返回 (List(2,4),List(1,3))

   • .find 方法和 .filter 方法很像，但是它返回满足给定条件的第一个元素，而不是所有元素。

     xs.find(f) 返回一个可选值。如果 xs 中存在一个元素 x 满足 f(x)=true，则返回 Some(x)；否则返回 None 。

     
     xxxxxxxxxx
     List(1,2,3,4).find(_ %2 ==0) // 返回 Some(2)
     List(1,2,3,4).find( _ <= 0)  // 返回 None

   • xs.takeWhile(f) 返回列表 xs 中连续满足 f(x)=true 的最长前缀。

     
     xxxxxxxxxx
     List(1,2,3,-1,4).takeWhile(_ >= 0) // 返回 List(1,2,3)

     而 xs.dropWhile(f) 去除列表 xs 中连续满足 f(x)=true 的最长前缀。

     
     xxxxxxxxxx
     List(1,2,3,-1,4).dropWhile(_ >= 0) // 返回 List(-1,4)

     而 xs.span(f) 将 takeWhile 和 dropWhile 合二为一，就像 splitAt 将 take 和 drop 合二为一一样。它返回一组列表：xs.span(f) 等价于 (xs.takeWhile(f), xs.dropWhile(f)) 。

4. 列表判断：

   • xs.forall(f) ：如果列表xs 中全部元素都满足 f 就返回 true，否则返回 false 。
   • xs.exists(f)：如果列表 xs 中存在元素满足 f 就返回 true，否则返回 false 。

   
   xxxxxxxxxx
   List( 1,2,3,4).forall( _ > 0 ) // 返回 true
   List(-1,2,3,4).forall( _ > 0 ) // 返回 false
   List(-1,2,3,4).exists( _ > 0 ) // 返回 true

5. 列表折叠：用某种操作符合并元素。如：

   
   xxxxxxxxxx
   sum(List(1,2,3,4)) // 等于 1+2+3+4 = 10
   product(List(1,2,3,4)) // 等于 1x2x3x4 = 24

   • 左折叠 (z /: xs)(op) ：以 z 为前缀，对列表元素以此连续应用 op 操作。

     
     xxxxxxxxxx
     (z /: List(a,b,c))(op) // 等于 op(op(op(z,a),b),c)
     //              op
     //             /   \
     //            op     c
     //           /   \
     //          op    b
     //         / \
     //        z   a

     左折叠会产生一颗向左的操作树。它从左向右折叠。

   • 右折叠 (xs :\ z)(op) ：以 z 为后缀，对列表元素以此连续应用 op 操作。

     
     xxxxxxxxxx
      (List(a,b,c) :\ z)(op) // 等于 op(a,op(b,op(c,z)))
     //              op
     //             /   \
     //            a     op
     //                 /   \
     //                b     op
     //                      / \
     //                     c   z

     右折叠会产生一颗向右的操作树。它从右向左折叠。

左折叠和右折叠的效率是相同的，不存在执行效率上的差异。

你也可以使用 foldLeft 和 foldRight 这两个方法名，它是定义在 List 类中的方法。

6. 列表拼接 xs ::: ys 的执行时间和第一个参数 xs 的长度成正比。因为需要找到 xs 的尾指针指向 ys 的头指针。获取尾指针的算法复杂度为 $ O(n) $ 、获取头指针的算法复杂度为 $ O(1) $ 。

7. 因为类型擦除， 所以 Scala 类型推断不能自动推断出正确的列表类型。

8. xs.sortWith(before) 用于对列表 xs 中的元素进行排序，其中 before 是一个用来比较两个元素的函数。

   before(x,y)：如果 x 应该排在 y 的前面，则返回 true。

7.4 List 伴生对象方法

1. 前面介绍的所有操作都是 List 类的方法，因此我们在每个具体的 List 对象上调用它们。还有一些方法是定义在全局可访问的 scala.List 上的，这是 List 的伴生对象。

   有一些操作是用于创建列表的工厂方法，另一些是对特定形状的列表进行操作。

2. List.apply：从给定元素创建列表。

   List(1,2,3) 仅仅是 List.apply(1,2,3) 的便利方式，二者等效。

   
   xxxxxxxxxx
   List.apply(1,2,3)

3. List.range：从数值区间创建列表。

   • List.range(from,until)：创建一个包含了从 from 开始递增到 until-1 的数的列表。结果不包含 until 。
   • List.range(from,until,step)：创建一个包含从 from 开始、步长为 step、不超过 until 的数的列表。步长可以为正，也可以为负。

   
   xxxxxxxxxx
   List.range(1,5)
   List.range(1,-5,-1)

4. List.fill：创建包含零个或者多个相同元素拷贝的列表。它接收两个参数：要创建的列表长度、需要重复的元素。两个参数各以不同的参数列表给出。

   
   xxxxxxxxxx
   List.fill(3)("a")

   如果给 fill 的参数多于 1个，那么它会创建多维列表，如：列表的列表、列表的列表的列表。多出来的参数放在第一个参数列表中。

   
   xxxxxxxxxx
   List.fill(2,3)("a") // List(List("a","a","a"),List("a","a","a"))

5. List.tabulate：根据给定的函数计算列表的元素。它也有两个参数列表，第一个参数列表给出列表的维度，第二个参数描述列表的元素。它和 List.fill 区别在于：List.tabulate 的元素值不再固定，而是根据函数计算而来，函数参数为被计算的元素的所处的位置（索引）。

   
   xxxxxxxxxx
   List.tabulate(5)(n => n*n) // List(0,1,4,9,16)
   List.tabulate(5,5)( - * _) 
   /*
   List(
     List(0,0,0,0,0)
     List(0,1,2,3,4)
     List(0,2,4,6,8)
     List(0,3,5,9,12)
     List(0,4,6,12,16)
   )
   */

6. List.concat：拼接多个列表。

   
   xxxxxxxxxx
   List.concat(List("a","b","c"),List("d")) // List("a","b","c","d")

7.5 同时处理多个列表

1. 可以通过对多个列表组成的元组调用 zipped 方法，然后执行 map/exists/forall 等操作，就可以同时处理多个列表。

   
   xxxxxxxxxx
   (List(1,2,3,4), List(11,12,13),List("a","b","c","d","e")).zipped.foreach{
     case (item1:Int,item2:Int,item3:String) 
       => println("%d,%d,%s".format(item1,item2,item3))
   }

   注意：zipped 方法把所有列表中同一个位置的元素zip 在一起，以最短的列表为基准。