鏈表VS MutableList在階

Question

下面，這些數據結構的兩個描述：（在階本書從編程）

鏈表

鏈表是由節點 的可變序列與下一個指針相關聯。在大多數語言中，null將被挑選爲空鏈接列表 。這對於Scala 集合不起作用，因爲即使是空序列也必須支持所有序列的方法 。特別是，LinkedList.empty.isEmpty應該返回true並且不會拋出NullPointerException異常 。空鏈表被編碼爲 而不是以特殊的方式：它們的下一個字段指向節點 本身。就像他們不可改變的親戚一樣，鏈接列表最好按順序運行 。此外，鏈接列表可以很容易地將 元素或鏈接列表插入另一個鏈接列表。

易變列表

甲MutableList由單鏈表連同指針 引用該列表的終端空節點。這使得列表 附加了一個持續的時間操作，因爲它避免了必須 遍歷列表以搜索其終端節點。 MutableList是 ，目前是Scala中mutable.LinearSeq的標準實現。

主要區別在於MutableList類型中最後一個元素的指針的添加。

問題是：什麼可能是寧願使用LinkedList而不是MutableList？嚴格來說（儘管有新的指針），並不是MutableList等效的，而且在使用過的內存很少（最後一個元素的指針）時更加實用？

Answer 1

由於MutableList包裝LinkedList，大多數操作涉及一個額外的間接步驟。請注意，包裝是指包含LinkedList（indeed two, because of the efficient last element lookup）的內部變量。所以鏈表是實現可變列表的必需構建塊。

如果您不需要預先安排或查找最後一個元素，那麼您可以只爲LinkedList。 Scala爲您提供了大量的數據結構選擇，因此最好的方法是首先製作所需的所有操作（及其首選效率）的清單，然後選擇最適合的操作。

通常，我建議您使用immutable structures，它們通常和可變的一樣高效，並且不會產生併發問題。