Scalaの構造共有リスト

Question

ScalaのListからの構造共有に関する質問があります。私はいくつかのインターネットでこの文章を読んだところ

リストはテールリストの構造的共有を実装しています。これは、多くの演算がゼロメモリまたは定数メモリのいずれかのコストであることを意味します。

しかし、私は本当にどのようにリストの操作の時間とメモリコストが削減されるのか理解していません。我々は時間with4別のリストを作成したい場合など

val mainList = List(3, 2, 1) 
val with4 = 4 :: mainList // O(1) 

のためだけではなく、O（1）とメモリコストの一つであるが、リストの操作のためだろうか、それは違うだろうか？私は長さ（）または逆（）を意味する...それはまだO（n）のように普通でしょうか？誰も私を説明してくれるでしょうか、もしあなたが本当に助けになるだろうか？ありがとうございました！

Answer 1

構造的共有による一定時間（O（1））で実行されるリストの操作は、先頭に（::）、先頭と末尾になります。他のほとんどの操作は線形時間（O（n））です。 lengthとreverseなどのmyList.headとmylist.tail、他のものは、線形時間されているよう

次の例は、4 :: myListは一定の時間で正しいです。

これは、他のすべてがO（n）なので、Listは、これらの操作だけを使用しない限り、ほとんどの場合、特に便利なコレクションではありません。

さまざまなコレクションのランタイム特性の概要については、http://docs.scala-lang.org/overviews/collections/performance-characteristics.htmlを参照してください。