我最近開始學習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