LinkedList的使用案例

本文僅討論scala.collection.mutable.LinkedList。其他的實現不是這個線程的主題。LinkedList的使用案例

我的問題是：這個類的用例是什麼？我發現它有可變結構和不可變結構兩種類型的問題，同時產生無結構的好處。我這樣說是因爲：

的API看起來對我來說，就好像它是一個不可改變的API（filter，map，drop，take等全部返回新LinkedList而不是做就地修改）
所有不可變鏈表的好處是，至少我想，不存在，即結構之間最大的共享，這是因爲它們仍然可變（通過var elem和var next。

所以basicly我們有一個線性的存取時間，線性AP掛起時間，線性空間等，沒有什麼可以在空間複雜性或代碼推理能力方面表現出來（除了O（1）預先計劃，但仍然是不可變列表的情況）。

我是否看不到這種結構的重要好處？我正在尋找客觀的度量和/或適用於這個類的用例。

2012-10-02 m09

看起來像一個不可變類的薄包裝。好處：編寫它的人能夠很快做到，而不用擔心引入錯誤？ – bdares

@bdares是什麼讓你覺得呢？我快速查看了源代碼，似乎沒有這樣的事情。 –

嗯......就像任何可變類型一樣，它可以從幾個指針引用，一旦編輯完成，變化將從所有指針中看到。這與時間複雜性無關。 – Oren

我想說的原因很複雜 - 鏈表類允許你持有對列表中間節點的引用，並在該節點使用insert或update，而不是通過該節點的頭部名單。

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

在我確切地知道其中一些序列的變化會發生（以上myReference）的應用程序，它的成本要少得多修改該位置不是將所有內容複製到那個位置會出現這種情況與immutable.List（即我只是在myReference之後插入一個新節點）。

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

這樣的應用的一個例子 - 一個L-system，你展開一個字符串的一部分。在原地插入新節點要比在每次需要擴展時複製整個字符串要便宜得多。

另一個原因是完備性 - 因爲DoubleLinkedList和LinkedListLike有許多共同的基礎設施，提供額外的LinkedList類來作爲一個低成本的標準庫的大小。

2012-10-02 15:44:34 axel22

足夠好的原因。雖然我想知道，爲什麼沒有像地圖，過濾器等原地成語的實現有什麼特別的原因？ – m09

關於這方面已經有很多討論。這部分是因爲許多不易實現或根本不可實現（部分是由於性能原因（不管信不信由你），就地更新並不總是比複製更新更快），並且由於命名問題。然而，有一種操作可以在可變序列上通用實現，也就是'transform' - 它簡單地在每個元素上調用'update'。 – axel22

它對我來說還是有道理的，但我還是想知道爲什麼這些實現可能會被使用的大多數通用特徵都是空的。無論如何，我認爲他們不太難以實現，並且減少API中的噪聲優於提供已經實現的實現。謝謝：） – m09

回答