斯卡拉：列表性能

Question

醫生說

時間：列表中包含了O（1）前插和頭/尾的訪問。大多數其他 操作都是O（n）列表中元素的數量。這個 包括基於索引的元素查找，長度，追加和逆向。

Docs「自豪地」提到大多數操作都是O（n）。即使它通過鏈表進行備份，長度和附加操作也可以很容易地保持一致。也不知道我是否明白爲什麼它不是雙向鏈表，這會使O（1）反向操作。

這是功能強大的巨無霸，不是嗎？

[編輯]哪個集合可以給我所有上述操作的O（1）？

Answer 1

不變性是答案。這是一個簡化版本的實施清單

trait List[+A] { 
    def prepend[A1 >: A](a:A1): List[A] 
} 
case class Cons[A](head: A, tail: List[A]) extends List[A] { 
    def prepend[A1 >: A](a:A1): List[A1] = Cons(a, this) 
} 
case object Nil extends List[Nothing] { 
    def prepend[A1 >: A](a:A1): List[A1] = Cons(a, Nil) 
} 

有了這個ADT，你可以預先安排但不能創建一個雙向鏈表。讓我們瑟爲例

val list1 = Cons(1, Cons(2, Nil)) 
val list2 = Cons(0, list1) 
val list3 = Cons(-1, list1) 

這不能被實現爲doublylinked列表，而當您創建列表2和項目list3

Answer 2

在大多數情況下，你應該使用一個向量而不是列表變異列表1的值。這裏是不同斯卡拉系列的性能比較：

http://docs.scala-lang.org/overviews/collections/performance-characteristics.html