Scala之List

浅浅的花香味﹌ 2022-04-25 02:52 150阅读 0赞

### 文章目录 ###

*  Scala之List
 *   *  数据结构
     *  List的基本操作
     *  List类的一阶函数
     *   *  :::
         *  length
         *  init and last
         *  reverse

# Scala之List #

## 数据结构 ##

scala.collection.immutable.List是有序集合的不可以变的链表,它是递归结构

它有两个实现的case class 'scala.Nil’和’scala.::,它们实现的抽象的成员 ‘isEmpty’,‘head’和’tail’  
Nil代表一个空的List, :: 操作是在list的前面拼接

val fruit = "apples" :: ("oranges"::("paers" :: Nil))
        val nums = 1 :: (2::(3::(4::Nil)))
        val nums2 = 1 :: 2::3::4::Nil
        val diag3 = (1::(0::(0::Nil))) ::
                    (0::(1::(0::Nil))) ::
                    (0::(0::(1::Nil))) :: Nil
        println("fruit:"+fruit)
        println("nums:"+nums)
        println("num2:"+nums2)
        println("diag3:"+diag3)

输入

fruit:List(apples, oranges, paers)
    nums:List(1, 2, 3, 4)
    num2:List(1, 2, 3, 4)
    diag3:List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1))

nums和nums2的定义是等价的

该类是后进先出(last-in-first-out, LIFO)、堆栈式访问模式的最佳选择。如果你需要其他的访问模式，例如随机模式或者先进先出(FIFO)，可以考虑其他比List更合适的集合。

**性能**

时间复杂度：对List的prepend,head和tail的 操作，时间复杂度是O(1)。List里面，其他元素个数的操作时间复杂度是O(n)。包括按下表访问元素，‘length’,‘append’和’reverse’

空间复杂度:List实现了tail的结构共享。这意味着很多操作要么是零消耗，要么是衡量内存消耗

val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
        val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
        val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList

**创建List的方式与模式匹配**

// Make a list via the companion object factory
        val days = List("Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday")
    
        // Make a list element-by-element
        val when = "AM" :: "PM" :: List()
    
        // Pattern match
        days match {
          case firstDay :: otherDays =>
            println("The first day of the week is: " + firstDay)
            println("The other days of the week are: " + otherDays)
          case List() =>
            println("There don't seem to be any week days.")
        }
        
        val List(a,b) = when
        println("a:" + a)
        println("b:" + b)

输入

The first day of the week is: Sunday
    The other days of the week are: List(Monday, Tuesday, Wednesday, Thursday, Friday, Saturday)
    a:AM
    b:PM

Note

List已不可变和结构共享为突出特点，因此如果使用正确的话，可以提供较优的性能。  
然而，注意，同一个List对象会有多个引用。，这意味着对象依赖于结构共享。序列化/反序列化后，共享的结构没有的，每个引用都会对一个list.

返回的集合类，通常用List\[B\]来表示，

## List的基本操作 ##

list的所有操作可以分为以下三类：

head 返回list的第一个元素  
tail 返回一个不包含第一个元素的list  
isEmpty 当list为空时返回 true

head和tail的方法只能被非空list使用，当我们使用一个空list的时候，会抛出异常：

scala> Nil.head
    java.util.NoSuchElementException: head of empty list

下面是关于list如何被处理，排序的一个简单例子。一种简单的方式是嵌入排序，如下：排序一个非空的list x::xs, 排序剩下的xs,并将第一个元素x放在结果的右边。对空List进行排序会生成空list,代码块如下：

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

使用模式匹配来完成插入式排序

def isort(xs:List[Int]) : List[Int] = {
        /**
          * 模式匹配的方式排序
          */
        xs match {
          case List() => List()
          case x :: xsrest => insert(xs.head, isort(xs.tail))
        }
      }
    
      def insert(x: Int, xs:List[Int]) : List[Int] = {
        xs match {
          case List() => List(x)
          case xsh :: xsrest => if(x <= xsh) x::xs
          else xsh :: insert(x, xsrest)
        }
      }

通常常，列表上的模式匹配比用方法分解它们更清楚，所以处理列表有限选择模式匹配。

## List类的一阶函数 ##

### ::: ###

联合两个集合

println((1::1::Nil):::(2::2::Nil))

输出

List(1, 1, 2, 2)

:::在List类里面是一个实现了的方法,也可以手动写一个方法连接两个list.

/** Adds the elements of a given list in front of this list.
       *  @param prefix  The list elements to prepend.
       *  @return a list resulting from the concatenation of the given
       *    list `prefix` and this list.
       *
       *  @usecase def :::(prefix: List[A]): List[A]
       *    @inheritdoc
       *
       *    Example:
       *    {
       {
       {List(1, 2) ::: List(3, 4) = List(3, 4).:::(List(1, 2)) = List(1, 2, 3, 4)}}}
       */
      def :::[B >: A](prefix: List[B]): List[B] =
        if (isEmpty) prefix
        else if (prefix.isEmpty) this
        else (new ListBuffer[B] ++= prefix).prependToList(this)

上面是List类提供下，new ListBuffer\[B\] ++= prefix是将List转为ListBuffer  
遍历list,元素一次放入ListBuffer中，注意 ListBuffer是mutable的。  
实现如下  
ListBuffer.scala

override def ++=(xs: TraversableOnce[A]): this.type = xs match {
        case x: AnyRef if x eq this      => this ++= (this take size)
        case _                           => super.++=(xs)
    
      }

Growable.scala

/** ${Add}s all elements produced by a TraversableOnce to this $coll.
       *
       *  @param xs   the TraversableOnce producing the elements to $add.
       *  @return  the $coll itself.
       */
      def ++=(xs: TraversableOnce[A]): this.type = {
        @tailrec def loop(xs: scala.collection.LinearSeq[A]) {
          if (xs.nonEmpty) {
            this += xs.head
            loop(xs.tail)
          }
        }
        xs match {
          case xs: scala.collection.LinearSeq[_] => loop(xs)
          case xs                                => xs foreach +=
        }
        this
      }

case xs: scala.collection.LinearSeq\[\_\] 是判断xs是否是该类型，此处判断的类型只能是参数定义中xs的类型的子集。

使用模式匹配也可以完成的  
原理:首先考虑期望输出的形状，然后计算各个部分  
的形状，在适当的地方使用算法的递归调用。最后,构建  
这些部分的输出。

def append[T](xs:List[T], ys:List[T]):List[T] = {
        xs match {
          case List() => ys
          case x::xsrest => x::append(xsrest, ys)
        }
      }
      
      println(append((1::2::3::Nil),(4::5::6::Nil)))

输出

List(1, 2, 3, 4, 5, 6)

### length ###

得到list的长度，即元素个数

List和数组不一样，求List的长度需要遍历list,因此花费的时间与list中元素的个数成正比。所以判断一个list是否为空时，使用xs.isEmpty会xs.length

通过tail遍历累计个数

/** The length of the $coll.
       *
       *  $willNotTerminateInf
       *
       *  Note: the execution of `length` may take time proportional to the length of the sequence.
       */
      def length: Int = {
        var these = self
        var len = 0
        while (!these.isEmpty) {
          len += 1
          these = these.tail
        }
        len
      }

### init and last ###

init返回除去最后一个元素的集合  
last集合的最后一个元素

last的实现方式是遍历集合得到最后一个元素

def last: A = {
        if (isEmpty) throw new NoSuchElementException
        var these = this
        var nx = these.tail
        while (!nx.isEmpty) {
          these = nx
          nx = nx.tail
        }
        these.head
      }

init的实现方式是创建一个Builder对象，Builder可以以增量方式构建集合。先设置集合大小，然后遍历list,依次将元素放入Builder里面

/** Selects all elements except the last.
       *  $orderDependent
       *  @return  a $coll consisting of all elements of this $coll
       *           except the last one.
       *  @throws UnsupportedOperationException if the $coll is empty.
       */
      def init: Repr = {
        if (isEmpty) throw new UnsupportedOperationException("empty.init")
        var lst = head
        var follow = false
        val b = newBuilder
        b.sizeHint(this, -1)
        for (x <- this) {
          if (follow) b += lst
          else follow = true
          lst = x
        }
        b.result
      }

init和list方法都需要遍历集合，而且需要的时间与集合长度成正比。所以我们在构建数据时，尽量考虑访问时 可以使用list的head方法，而不是last方法。

### reverse ###

得到逆序的集合  
利用head和tail遍历，使用::来组成一个逆序的集合。

override def reverse: List[A] = {
        var result: List[A] = Nil
        var these = this
        while (!these.isEmpty) {
          result = these.head :: result
          these = these.tail
        }
        result
      }

GenSeqLike.scala重写了equals方法

/** The equals method for arbitrary sequences. Compares this sequence to
       *  some other object.
       *  @param    that  The object to compare the sequence to
       *  @return   `true` if `that` is a sequence that has the same elements as
       *            this sequence in the same order, `false` otherwise
       */
      override def equals(that: Any): Boolean = that match {
        case that: GenSeq[_] => (that eq this.asInstanceOf[AnyRef]) || (that canEqual this) && (this sameElements that)
        case _               => false
      }

所以xs.reverse equals xs.reverse.reverse的值为true  
而 xs.reverse eq xs.reverse.reverse的值为false

逆序也能使用:::来实现，如下

def myReverse[T](xs:List[T]):List[T] = {
        xs match {
          case List() => Nil
          case x::xsrest => myReverse(xsrest):::List(x)
        }
      }