Scala中List与ListBuffer的append、concat操作性能有何差异？

核心结论 #

绝大多数常规场景下，ListBuffer的非索引单元素追加、批量拼接操作性能都显著高于不可变List的对应操作。

认知修正与细节补充 #

针对你之前的认知做几点校正和补充：

• 你对不可变List的操作认知完全正确：List是不可变的单链表结构，所有尾部追加、多列表拼接操作都会遍历整个原列表，生成全新的列表对象，时间复杂度固定为O(n)，n是原列表长度；批量拼接:::还要额外遍历待拼接的列表，总复杂度为O(n+m)，m是待拼接列表长度。如果在循环中反复做尾部追加，总复杂度会达到O(n²)，数据量稍大时性能损耗非常明显。
• 你对ListBuffer的操作认知有一点小误差：ListBuffer内部是带尾指针的可变数组实现，+=单元素追加的平摊时间复杂度是O(1)，只有底层数组扩容时才会复制现有元素，扩容的平摊成本极低。
• 对于++批量拼接操作：如果待拼接的元素数量小于ListBuffer的剩余空闲空间，会直接把所有元素复制到底层数组的空闲位置，时间复杂度只有O(m)（m是待拼接元素的数量），不需要复制原ListBuffer的任何元素，这一点和List的:::需要复制所有原列表元素有本质区别，性能差距极大。只有当待拼接元素数量超过剩余空间需要扩容时，才会复制原有元素，哪怕是这种场景，ListBuffer的扩容也是指数级扩容，平摊成本还是远低于List每次拼接都全量复制的成本。

特殊场景说明 #

只有一种极端场景下二者性能差距不大：你每次拼接都是直接把新元素接在原List的头部，也就是用::操作，这个操作List的复杂度是O(1)，不需要遍历原列表，但这种场景不属于你问的尾部追加/拼接的范围。

内容的提问来源于stack exchange，提问作者user16367669