斯卡拉：列表性能

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