为什么追加到列表不好？
我最近开始学习scala，并且遇到了:: :（cons）函数，这个函数前面是一个列表。
在“Scala编程”一书中，它指出不存在追加函数，因为追加到列表的性能为o（n），而预先计算的性能为o（1）
有些事情让我觉得这个说法是错误的。
性能是否依赖于实现？ 是不是可以简单地实现与前进和后退链接的列表，并将第一个和最后一个元素存储在容器中？
我想第二个问题是当我有一个列表时，我应该做什么，说1,2,3，我想添加4到最后？
关键是x :: somelist不会改变somelist ，而是创build一个新的列表，其中包含x，后面跟着somelist的所有元素。 这可以在O（1）时间内完成，因为只需要在新创build的单独链接列表中将somelist设置为x的后继。
如果使用双向链接列表， x也必须设置为somelist的前端，这将修改somelist 。 所以如果我们想在O（1）中能够做到::而不修改原始列表，我们只能使用单个链表。
关于第二个问题：您可以使用:::将单个元素列表连接到列表的末尾。 这是一个O（n）操作。
List(1,2,3) ::: List(4)
其他答案已经给这个现象提供了很好的解释。 如果将多个项目附加到子例程的列表中，或者如果通过追加元素来创build列表，则一个function性的习惯用法是以相反的顺序构build列表，包括列表前面的项目，然后倒在最后。 这给你O（n）性能，而不是O（n²）。
预先考虑更快，因为它只需要两个操作：
- 创build新的列表节点
- 让新的节点指向现有的列表
追加需要更多的操作，因为你只需要一个指向头部的指针就可以遍历列表的末尾。
我以前从来没有在Scala中编写过程序，但可以尝试一个List Buffer
由于问题刚刚更新，值得注意的是事情已经改变了。
在今天的Scala中，您可以简单地使用xs :+ x在任何顺序集合的末尾附加一个项目。 （也有x +: xs前置，Scala的2.8+以上的收集操作的助记符是col on旁边的收集。）
这将是O（ n ）与List或Seq的默认链接实现，但是如果使用Vector或IndexedSeq ，则这将是有效的恒定时间。 Scala的Vector可能是Scala最有用的类列表集合，不像Java的Vector现在几乎没有用。
如果你正在Scala 2.8或更高版本工作， collections介绍是绝对必读的。
大多数函数式语言突出显示单链表数据结构，因为它是一个方便的不可变的集合types。 当你用function语言来说“list”时，通常就是你的意思（一个单链表，通常是不可变的）。 对于这种types，追加是O（n），而缺点是O（1）。
