scala - scala中的LinkedList vs MutableList

Question

下面，对这些数据结构的两种描述：（来自Programming in scala book）

链表

链表是由与下一个指针链接的节点组成的可变序列。在大多数语言中，null 将被选为空链表。这不适用于 Scala 集合，因为即使是空序列也必须支持所有序列方法。特别是 LinkedList.empty.isEmpty 应该返回 true，而不是抛出 NullPointerException。空链表以特殊方式编码：它们的下一个字段指向节点本身。像它们的不可变表亲一样，链表最好按顺序操作。此外，链表可以很容易地将一个元素或链表插入另一个链表。

可变列表

MutableList 由一个链表和一个指向该链表终端空节点的指针组成。这使得 list append 成为一个恒定时间的操作，因为它避免了遍历列表来寻找它的终端节点。MutableList 目前是 Scala 中 mutable.LinearSeq 的标准实现。

主要区别是在MutableList类型中添加了最后一个元素的指针。

问题是：什么可能是使用更喜欢LinkedList而不是MutableList？严格来说（尽管有新的指针）不是MutableList等效的，甚至更实用的是只增加了一点使用的内存（最后一个元素的指针）？

Answer 1

由于MutableList包装了 a LinkedList，大多数操作都涉及一个额外的间接步骤。请注意，包装意味着，它包含 a 的内部变量LinkedList（实际上是两个，因为高效的最后一个元素查找）。所以链表是实现可变链表的必要组成部分。

如果您不需要预先添加或查找最后一个元素，那么您可以只使用LinkedList. Scala 为您提供了大量的数据结构选择，因此最好首先列出您需要的所有操作（以及它们的首选效率），然后选择最合适的。

通常，我建议您使用不可变结构，它们通常与可变结构一样高效，并且不会产生并发问题。