我最近开始学习scala，并且我遇到了::（cons）函数，它的前缀是一个列表。
在著作“编程在斯卡拉”它指出，没有附加的功能，因为附加到一个列表具有性能O（N），而在前面加上为O的性能（1）为什么追加到列表不好？
东西只是令我错了该声明。
性能是否依赖于实现？难道仅仅通过向前和向后链接实现列表并将第一个和最后一个元素存储在容器中是不可能的？
我想第二个问题是我应该做什么，当我有一个列表，说1,2,3，我想添加4到它的末尾？
关键是x :: somelist不会变异somelist，而是创建一个新的列表，其中包含x，其后跟所有元素somelist。这可以在O（1）时间内完成，因为您只需在新创建的单链表中将somelist设置为x的后继。
如果使用双向链接列表，x也必须设置为somelist的前导，它将修改somelist。因此，如果我们希望能够在O（1）中执行::而不修改原始列表，那么我们只能使用单个链接列表。
关于第二个问题：您可以使用:::将单个元素列表连接到列表的末尾。这是一个O（n）操作。
List(1,2,3) ::: List(4)
预谋更快，因为它只需要两个操作：
追加需要更多的操作，因为你有遍历到列表的末尾，因为你只有一个指向头部的指针。
我从来没有用Scala编程之前，但你可以尝试一个List Buffer
大多数函数式语言占有突出的地位单链接列表的数据结构，因为它是一个方便的不可变的集合类型。当你用功能语言说“list”时，这通常就是你的意思（一个单链表，通常是不可变的）。对于这种类型，追加是O（n），而缺点是O（1）。
其他答案对这种现象给出了很好的解释。如果将多个项目附加到子例程的列表中，或者如果通过附加元素创建列表，则功能方式是按照相反的顺序构建列表，包括列表的正面上的项目，然后在最后反转它。这给你O（n）的表现而不是O（n²）。
由于问题刚刚更新，值得注意的是事情在这里发生了变化。
在今天的Scala中，您可以简单地使用xs :+ x在任何顺序集合的末尾追加一个项目。 （也有x +: xs前面加上。许多Scala的2.8+收集操作的记忆是，山坳那张旁边山坳经文。）
这将是O（ñ）与默认链接执行List或Seq，但是如果您使用Vector或IndexedSeq，这将有效地保持一定的时间。 Scala的Vector可能是Scala最有用的类列表集合 - 不像Java的Vector这几天大多没用。
如果您使用的是Scala 2.8或更高版本，那么collections introduction是绝对必读的。
“性能是否依赖于实现？”：不要忘记'List'是Scala中的具体类，并且与Java'List'接口无关。 – krookedking 2014-07-29 16:19:03