java - 为什么 Scala List 没有 size 字段？

Question

来自 Java 背景，我想知道为什么 Scala 中的 List 没有像 Java 等效的 LinkedList 那样的 size 字段.毕竟，有了 size 字段，您就可以在恒定时间内确定列表的大小，那么为什么要删除 size 字段呢？

(这个问题指的是 Scala 2.8 及更高版本中的新集合类。另外，我指的是不可变的 List，而不是可变的。)

Answer 1

不能说尺寸字段已删除，因为自从 LISP 以来，没有尺寸的列表已经存在了 50 年，它们无处不在，它们在 ML 和 Haskell 中也很常见，两者都有影响力斯卡拉。

根本原因是list是递归结构。非空 List 是 Cons(head: A, tail: List[A]) — 除了 Cons实际上称为 :: 以允许方便的中缀表示法。您可以访问尾部(没有头部元素的列表)，这也是一个列表。这几乎一直都在进行。因此，在列表中包含计数并不意味着只添加一个整数，而是添加与元素一样多的整数。这是可行的，但肯定不是免费的。

如果和java的LinkedList比较，LinkedList有一个递归实现(基于Node，或多或少像Cons，但有双向链接)。但是 LinkedList 不是节点，它拥有它们(并保留它们的数量)。因此，虽然它具有递归实现，但您不能递归地对待它。如果您希望将 LinkedList 的尾部作为 LinkedList，则必须删除头部并更改列表，或者将所有尾部元素复制到新的 LinkedList。所以scala的List和java的LinkedList是很不一样的结构。