私は最近、スカラの学習を始めました。リストの先頭にある::（cons）関数に出くわしました。リストに追加する前に付けるのに対し、パフォーマンスのO（n）を持っているので、それが何のアペンド機能が存在しないと述べている本「スカラ座でのプログラミング」では
は、Oの性能を有する（1）リストに追加するのが悪いのはなぜですか？
何かがちょうど約間違っているとして私を打ちますその声明。
パフォーマンスは実装に依存しませんか？順方向リンクと逆方向リンクの両方でリストを実装し、最初と最後の要素をコンテナに格納することはできませんか？
2番目の質問は、私がリストを持っているとき、1,2,3と言い、4の最後に追加したいと思っていることです。それだけで2つの操作を必要とするため
x :: somelistはsomelistに変更されていませんが、代わりにsomelistのすべての要素が続くxを含む新しいリストが作成されます。新しく作成された単一リンクリストのxの後継としてsomelistを設定するだけで済み、O（1）時間で実行できます。
二重リンクリストが代わりに使用された場合は、somelistを変更するsomelistの頭の先祖としてxを設定する必要があります。したがって、O（1）に::を元のリストを変更せずに実行できるようにしたい場合は、単独でリンクされたリストしか使用できません。
2番目の質問について：:::を使用すると、単一要素リストをリストの末尾に連結できます。これはO（n）操作です。
List(1,2,3) ::: List(4)
前に付けるには速いです：
追加に新しいノードポイントは、より多くの操作が必要であることを持って、新しいリストのノードを作成します。あなたが頭へのポインタしか持っていないので、リストの終わりまでトラバースすることができます。
私は前にScalaでプログラムされたことがありませんが、あなたはそれが便利な不変コレクション型だとしてList Buffer
ほとんどの関数型言語が目立つ、重リンクリストデータ構造を把握してみてください可能性があります。関数型言語で "リスト"と言うと、それは一般的にあなたが意味するものです（単一リンクリスト、通常不変です）。このような型の場合、appendはO（n）であり、consはO（1）です。
この現象については、他の回答からも良い説明があります。サブルーチンのリストに多くのアイテムを追加する場合、または要素を追加してリストを作成する場合、機能的なイディオムは、逆順でリストを構築し、リストのの前に最後にそれを逆にします。これにより、O（n）の代わりにO（n）のパフォーマンスが得られます。
質問が更新されたので、ここで変更されている点に注目してください。
今日のScalaでは、xs :+ xを使用して、順次コレクションの最後にアイテムを追加することができます。 （前に付加するx +: xsもあります。Scalaの2.8+コレクション操作の多くのニーモニックが上COLがCOL lectionの隣に移行すること。）
これは、O（N）となりますListまたはSeqの既定のリンク先の実装ですが、VectorまたはIndexedSeqを使用すると、これは事実上一定の時間になります。 ScalaのVectorは、おそらくScalaの最も有用なリストのようなコレクションで、JavaのVectorとは異なり、最近ではほとんど役に立たない。
Scala 2.8以降で作業している場合、collections introductionは絶対に読み込む必要があります。
"実装はパフォーマンスに依存しないのですか？"：リストはスカラの具象クラスであり、Javaの 'List'インタフェースとは関係ありません。 – krookedking