13

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

私の質問は: このクラスのユースケースは何ですか? 私は、可変タイプと不変タイプの構造の両方の問題を抱えている一方で、メリットがないことを発見しました。私がそう言うのは：

  • APIは、不変のAPIであるかのように見えます（filter、map、などはすべてdrop、インプレース変更を行うのではなくtake、新しいものを返します）LinkedList
  • 不変のリンクされたリストのすべての利点は、少なくとも私が推測するに存在しないと思います。つまり、構造間の最大の共有var elemですvar next。

したがって、基本的には、線形アクセス時間、線形追加時間、線形スペースなどがありますが、スペースの複雑さやコードについて推論する能力については何も示していません (おそらく O(1) プリペンドを除くが、不変リストの場合は依然としてそうです)。 .

このタイプの構造の重要な利点を見落としていませんか? このクラスに適用できる客観的な尺度やユースケースを探しています。

4

1 に答える 1

5

その理由は複雑さだと思います。リンクされたリスト クラスを使用すると、リストの先頭を通過する代わりに、リストの途中にあるノードへの参照を保持し、そのノードでinsertorを使用できます。update

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

シーケンスの変更がどこで発生するかが正確にわかっているアプリケーション (myReference上記) では、その場所を変更するコストは、すべてをその場所にコピーする場合のようにimmutable.List(つまり、新しいノードを後で挿入するだけですmyReference)よりもはるかに少なくなります。 .

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

そのようなアプリケーションの例 -文字列の一部を拡張するL システム。拡張が必要になるたびに文字列全体をコピーするよりも、新しいノードをその場で挿入する方がはるかに安価です。

もう 1 つの理由は完全性です。とは多くの共通インフラストラクチャを共有しているため、追加DoubleLinkedListのクラスを提供することで標準ライブラリのサイズを小さくすることができました。LinkedListLikeLinkedList

于 2012-10-02T15:44:34.020 に答える