LinkedListの使用例

Question

この投稿はscala.collection.mutable.LinkedListについて書かれています。他の実装はこのスレッドのトピックではありません。

私の質問は：このクラスのユースケースは何ですか？私はそれが可変でも不変でもないタイプの構造の問題を抱えているのに対し、何の利益ももたらさないことがわかります。私はので、と言う：それは不変のAPI（filter、map、drop、takeなど全てがインプレース変更を新しいLinkedListを返す代わりにやって）

であるかのように

• APIは、私には見えるすべて不変のリンクリストの利点は、それらがvar elemとvar nextて（まだ変更可能ですので、少なくとも私は、すなわち構造物との間の最大の共有、存在しないと思い、ある。

のでbasicly我々は、線形アクセス時間を持って、リニアAP （O（1）の前置詞を除いていますが、まだ不変なリストの場合もあります）。

このタイプの構造の重要な利点を確認できませんか？私は客観的な尺度やユースケースをこのクラスに適用可能なものとして探しています。

Answer 1

私はその理由が複雑だと言いたいと思います。リンクリストクラスでは、リストの途中でノードへの参照を保持し、そのノードではinsertまたはupdateを使用します。リスト。私は場所を正確に、いくつかの配列の変化は、（myReference上記）が起こることを知っているアプリケーションで

[] --> [] --> ... --> [] --> ... --> [] --| 
^     ^
head     myReference 

immutable.Listの場合のように、（その場所にすべてをコピーするよりも、その場所を変更するには、はるかに少ないコストつまり、私はちょうどmyReferenceの後に新しいノードを挿入します）。

       myNewNode 
          v 
[] --> [] --> ... --> [] --> [] ---> ... --> [] --| 
^     ^
head     myReference 

このようなアプリケーションの例 - 文字列の一部を展開するL-system。展開する必要があるたびに文字列全体をコピーするよりも、新しいノードをインプレースに挿入するほうがはるかに安いです。

もう一つの理由は、完全である - DoubleLinkedListとLinkedListLikeので、余分なLinkedListクラスを提供し、共通のインフラストラクチャの多くを共有するには、標準ライブラリのサイズに低コストとして来ました。