为什么追加到列表不好？

Question

我最近开始学习scala,并且我遇到了::(cons)函数,它在一个列表前面.
在"Scala编程"一书中,它指出没有附加函数,因为附加到列表具有性能o(n)而前置函数具有o(1)的性能

有些事情让我觉得这个说法错了.

性能是否依赖于实现？是不是可以简单地使用前向和后向链接实现列表并将第一个和最后一个元素存储在容器中？

我想的第二个问题是,当我有一个列表时,我应该做什么,比如说1,2,3,我想在它的末尾添加4个？

Answer 1

关键是x :: somelist不变异somelist,而是创建一个新的列表,其中包含x后跟所有元素somelist.这可以在O(1)时间内完成,因为您只需要设置somelist为x新创建的单链表中的后继.

如果使用双重链接列表,则x还必须将其设置为somelist头部的前身,这将进行修改somelist.因此,如果我们希望能够::在不修改原始列表的情况下在O(1)中执行,我们只能使用单链接列表.

关于第二个问题:您可以使用:::将单个元素列表连接到列表的末尾.这是O(n)操作.

List(1,2,3) ::: List(4)

Answer 2

其他答案对这一现象给出了很好的解释.如果要将多个项目附加到子例程中的列表中,或者如果要通过附加元素创建列表,则功能习惯用法是以相反的顺序构建列表,同时列出列表前面的项目,然后最后扭转它.这给你O(n)性能而不是O(n²).

Answer 3

由于这个问题刚刚更新,值得注意的是这里的情况发生了变化.

在今天的Scala中,您可以简单地使用xs :+ x在任何顺序集合的末尾附加项目.(还有x +: xs前面加上.许多Scala的2.8+收集操作的记忆方法是在山坳上的信息放进旁边的山坳经文.)

这将是O(n)与默认链接的实现List或Seq,但如果你使用Vector或IndexedSeq,这将是有效的恒定时间.Scala Vector可能是Scala最有用的列表式集合 - 与Java不同Vector,现在这些集合几乎没用.

如果您使用的是Scala 2.8或更高版本,则必须阅读集合介绍.

Answer 4

前置更快,因为它只需要两个操作:

追加需要更多操作,因为您必须遍历到列表的末尾,因为您只有指向头部的指针.

我以前从未在Scala中编程,但您可以尝试使用List Buffer

Answer 5

大多数功能语言突出显示一个单链表数据结构，因为它是一种方便的不可变集合类型。用功能语言说“列表”时，通常就是您的意思（单链接列表，通常是不可变的）。对于这种类型，append为O（n），而cons为O（1）。