使用哪个可变的Scala列表？

Question

这是关于No Scala mutable list 的后续问题。

我想在Scala中使用可变列表。我可以选择以下列表：

• scala.collection.mutable.DoubleLinkedList
• scala.collection.mutable.LinkedList
• scala.collection.mutable.ListBuffer
• scala.collection.mutable.MutableList

这很不错，但什么是“标准的”、推荐的、惯用的Scala方式？我只想使用一个可以在后面添加元素的列表。

在我的情况下，我正在使用HashMap，其中“列表”（我是以一般意义上的列表来理解它）将位于值的一侧。然后，我从文件中读取一些内容，对于每一行，我想在哈希映射中找到正确的列表，并将该值添加到列表中。

- Karel Bílek

---

你可能需要详细说明你将如何使用它 - 因为从一般意义上讲，Scala 的惯用方式并不是使用可变列表（而是使用不可变列表的折叠或递归）。 - Andrzej Doyle

我认为你的列表可以是不可变的。你可以简单地将一个不可变的列表前置，并将你的HashMap条目更新为这个新创建的列表。 - ziggystar

那么，在这种情况下，我将不得不更改哈希映射而不是列表。目前，我不更改哈希映射，但我更改列表。 - Karel Bílek

请参见https://dev59.com/Tm035IYBdhLWcg3wZvFg，了解ListBuffer和MutableList之间的区别。 - Mike

Answer 1

取决于您需要什么。

DoubleLinkedList是一种链表，允许您在节点列表中前后移动。使用它的prev和next引用分别转到前面或后面的节点。

LinkedList是一个单向链表，因此没有prev指针 - 如果您只需不断遍历列表的下一个元素，则需要使用它。

编辑：请注意，上述两个旨在作为更复杂的列表结构（如支持高效附加的MutableList和mutable.Queue）的内部构建块使用。

上述两个集合都具有线性时间的追加操作。

ListBuffer是一个缓冲区类。虽然它由单向链表数据结构支持，但它不会将next指针公开给客户端，因此您只能使用迭代器和foreach遍历它。 然而，它主要用作缓冲区和不可变列表构建器 - 您可以通过+=将元素附加到它上面，并且当您调用result时，可以非常高效地获得功能性的immutable.List。与可变和不可变列表不同，追加和预先附加操作都是常数时间 - 您可以通过+=在末尾高效地附加。

MutableList通常用于内部使用，除非您计划基于单向链表数据结构实现自定义集合类。例如，可变队列继承了此类。因为它维护对列表中最后一个节点的引用，所以MutableList类还具有有效的常数时间追加操作。

- axel22

---

我在文档中没有找到关于“哪个列表最适合删除元素”的答案，例如，如果我计划构建一个列表，然后一次删除大量项目？ - Hamy

我找到了这个页面，因为我也想知道标准、推荐、惯用的方法。从这个详细的解释中，我的印象是答案是ListBuffer。 - Jim Pivarski

答案是使用ListBuffer。它不仅效率高，而且最终可以生成不可变的List对象，这相当符合语言习惯。其他列表并不常用。 - axel22

线性附加... 为什么会有人使用它？如果Scala想要被认真对待，就需要摆脱象牙塔的思维方式，更加务实。 - Eric Hartford

“象牙塔”是一个相当强烈的说法。标准库中的类LinkedList确实有用途，那就是构建更高层次的抽象。在Scala中，LinkedList基本上是一个链表节点，因此是像双向链接的队列、MutableList和循环列表（即环）这样的类的构建块。在每个列表节点中存储长度、最后一个节点和类似的信息是没有意义的。注意：LinkedList并不是直接用于典型客户端代码的 -- MutableList、Queue、immutable.ListBuffer和immutable.List才是。 - axel22

Answer 2

文档的 Concrete Mutable Collection Classes 页面（或 2.12 版本）概述了可变列表类，包括何时使用哪个列表的说明。

- Daniel Werner

---

太好了！我正在考虑接受这个答案，三年后。 - Karel Bílek

已接受。对@axel22表示抱歉，但他在2012年尽了最大努力。 - Karel Bílek

所引用的页面已经更新到2.13版本： https://docs.scala-lang.org/overviews/collections-2.13/concrete-mutable-collection-classes.html - Reid Spencer

@ReidSpencer 已更新，谢谢。下次可以自己更新答案。 - Daniel Werner

Answer 3

如果你想要添加项目，就不应该使用 List。当你想要在前面添加项目时，List 是很好的选择。相反，你应该使用 ArrayBuffer。

- drexin

---

我不同意。如果您不需要随机访问，ListBuffer 比 ArrayBuffer 具有更好的性能特征，因为 ArrayBuffer 需要不时地进行大小调整。当然，添加操作可能会以分摊常数时间运行，这并不太糟糕，但我在这里看不到 ArrayBuffer 的任何优势。 - rolve

“分摊常数时间”通常最终会更快，因为在JVM上分配新对象（并处理相关的垃圾回收压力）所涉及的常数非常高，而重新调整大小操作极其罕见（平均每个项目只需复制两次）。更不用说ArrayBuffer的缓存局部性好处，在现代CPU上可能非常巨大。 - John Colanduoni

自从我发表评论以来已经过去了近3年，我同意 ArrayBuffer 可能是更好的选择。无论如何，实际的性能测量应该作为讨论的基础。 :) - rolve

Answer 4

我只想使用一个可以在后面添加东西的列表。

那么选择实现Growable的东西。我个人建议其中一个Buffer实现。

我避免使用LinkedList和DoubleLinkedList，因为它们主要作为其他集合的底层实现，但在Scala 2.9.x之前存在相当多的错误。从Scala 2.10.0开始，我期望各种错误修复已经将它们提升到标准。不过，它们缺少一些人们期望的方法，例如+=，你会在基于它们的集合中找到这些方法。

- Daniel C. Sobral