List類(lèi)的原理
-
-
List算是Scala中最常用的結(jié)構(gòu)护锤。是一個(gè)抽象類(lèi)照筑，有子類(lèi)::和Nil組成，List的類(lèi)型參數(shù)是協(xié)變的措伐，列表的所有操作都可以通過(guò)以下三種操作進(jìn)行定義：
def isEmpty: Boolean def head: T def tail: List[T]Nil對(duì)象定義了一個(gè)空列表，Nil對(duì)象繼承自List[Nothing]军俊，也就是說(shuō)Nil和任何列表都是兼容的废士，是任何列表的子類(lèi)元素。Nil的head和tail對(duì)象都會(huì)拋出異常蝇完，因?yàn)闆](méi)有值是Nothing類(lèi)型的。::類(lèi)矗蕊，cons類(lèi)表示非空列表短蜕，為了支持中綴::實(shí)現(xiàn)模式匹配。在模式匹配中傻咖，每個(gè)中綴操作數(shù)都被當(dāng)做是入?yún)?lái)調(diào)用中綴操作符對(duì)應(yīng)的構(gòu)造方法朋魔。x :: xs = ::(x,xs)，::中的head和tail直接返回構(gòu)造參數(shù)中的對(duì)應(yīng)部分卿操。 -
-
- 代碼
實(shí)現(xiàn)了三個(gè)函數(shù)警检，原因如下，在final case class ::[T](head: T, tail: List[T]) extends List[T] { override def isEmpty: Boolean = false }Scala的樣例類(lèi)中害淤，每一個(gè)類(lèi)參數(shù)都是類(lèi)字段扇雕，Scala允許使用字段來(lái)實(shí)現(xiàn)抽象的無(wú)參方法。因此直接實(shí)現(xiàn)了head和tail參數(shù)窥摄。 -
List的其他方法基本都可以基于這三個(gè)方法實(shí)現(xiàn)镶奉。
-
-
:::的實(shí)現(xiàn)不是很懂？
-
ListBuffer
-
ListBuffer允許對(duì)列表的元素在尾部做累加進(jìn)行修改崭放，可以使用buf += elem的操作在buf尾部添加elem元素哨苛，一旦添加完成，可以使用toList操作將緩沖轉(zhuǎn)換為列表币砂。列表緩沖在追加操作+=和toList操作上都只消耗很短的常量時(shí)間建峭。
-
-
List類(lèi)的大多數(shù)方法的真實(shí)實(shí)現(xiàn)并沒(méi)有使用遞歸，而是通過(guò)循環(huán)和列表緩沖决摧。toList的操作只會(huì)有少量計(jì)算周期的開(kāi)銷(xiāo)亿蒸，和列表的長(zhǎng)度無(wú)關(guān)凑兰。
-
-
List的實(shí)現(xiàn)中涉及到了可變?cè)兀?code>List在外面看是純函數(shù)式的，但實(shí)際實(shí)現(xiàn)用到了可變的列表緩沖祝懂，這是Scala編程的一個(gè)策略票摇，高效而且方便使用。
-
