爲什麼要在Scala List中添加一個常量時間操作，但追加了一個線性時間操作？

Question

我從Odersky的的「在Scala編程」學習Scala現在的中間，我剛剛看了這個

...需要追加到列表中的時間與 的大小線性增長列表，而預先考慮::需要一個固定的時間...

爲什麼要花費線性時間來追加到列表上，而只有一個常量時間才能附加到列表上。我目前的猜測是它以某種方式作爲鏈接列表在內部實施，這將解釋兩種操作之間的差異。在那種情況下，如何實現具有恆定時間的ListBuffers？

Answer 1

它們的實現方式與鏈接列表類似。區別在於ListBuffer還包含一個指向列表尾部的指針。 Scala的源代碼是開放的，如果您想了解它的細節，你可以探索它在github（例如，這裏是ListBuffer的追加代碼）

Answer 2

這裏有兩個問題：一個是關於列出一個很基本的一個，另一個是scala特有的。首先，我會畫一幅畫。 「List」抽象數據類型是計算機科學中最古老的一種;它回溯到1956年並且是LISP語言的首次實施。

列表ADT實際上是使用單向鏈表實現的。每個元件傳統上稱爲一個cons單元（無指示列表的結束）：

+------+------+  +------+------+ +--------+ 
| 1 | * -+----> | 3 + * -+--->| NIL | 
+------+------+  +-------------+ +--------+ 
^ 
| 
val list1 

這對應於鏈式「缺點」（列表構造）調用在階：

scala> val list1 = 1 :: 3 :: Nil 
list1: List[Int] = List(3, 1) 

列表是一個不可變數據結構。我們不能通過重寫任何 現有的指針/引用來破壞性地更新它。那麼，如果我們想補充它呢？

scala> val list2 = 0 :: list1 
list2: List[Int] = List(0, 1, 3) 

創建列表2是非常快速和容易的，我們只需要創建一個新的利弊細胞和它前面加上現有的列表：

+------+------+  +------+------+  +------+------+ +--------+ 
| 0 | *--+----->| 1 | * -+----> | 3 + * -+--->| NIL | 
+------+------+  +------+------+  +-------------+ +--------+ 
^     ^
|     | 
val list2   val list1 

這樣做的好處是，它讓所有現有的引用不變，保持不變性。但是，如果我們想/ append /到列表中，我們將不得不將參數覆蓋到新元素，從而改變list1。因此，要做到這一點的唯一方法是複製整個現有的列表，從而把它改寫：

scala> val list3 = list1 ++ (5 :: Nil) 
list3: List[Int] = List(1, 3, 5) 


+------+------+  +------+------+  +------+------+ +--------+ 
| 0 | *--+----->| 1 | * -+----> | 3 + * -+--->| NIL | 
+------+------+  +------+------+  +-------------+ +--------+ 
^     ^          ^
|     |           | 
val list2   val list1         | 
                   | 
                   | 
(copy)               | 
+------+------+  +------+------+ +--------+-------+  | 
| 1 | * -+----> | 3 + * -+--->| 5 | *--+-------+ 
+------+------+  +-------------+ +--------+-------+  
^ 
| 
val list3 

這是一個線性時間的操作，因爲，要附加到長度爲N的列表，我們必須讓所有的副本N cons單元（除Nil外）。

至於scala的ListBuffer，它的append通過直接改變後備列表來工作，重寫最後一個cons單元的尾部引用，它具有看起來很尷尬的類型:: [A]。

在List.scala：

final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] { 
  override def tail : List[B] = tl 
    override def isEmpty: Boolean = false 
} 

[..] 在ArrayList中。階：

/** Appends a single element to this buffer. This operation takes constant time. 
* 
* @param x the element to append. 
* @return this $coll. 
*/ 
def += (x: A): this.type = { 
    if (exported) copy() 
    if (isEmpty) { 
    last0 = new :: (x, Nil) 
    start = last0 
    } else { 
    val last1 = last0 
    last0 = new :: (x, Nil) 
    last1.tl = last0 
    } 
    len += 1 
    this 
} 

last1.tl = last0被允許的，因爲:: T1具有可視性私人[階]，「發動機罩下」操作允許不安全的突變集合，如ListBuffer。