MutableList和ListBuffer之間的區別

斯卡拉的MutableList和ListBuffer類在scala.collection.mutable之間有什麼區別？你什麼時候使用一個和另一個？MutableList和ListBuffer之間的區別

我的用例是有一個線性序列，我可以有效地刪除第一個元素，prepend和append。這個最好的結構是什麼？

2011-03-27 Mike

關於它們如何工作的一點說明。

ListBuffer內部使用Nil和::建立一個不可變List並允許恆定時間除去第一的和最後元件。爲此，它會在列表的第一個和最後一個元素上保留一個指針，並且實際上允許更改（否則不可變的）類的頭部和尾部（private[scala] var成員允許的好的技巧）。它的toList方法在常量時間內也返回正常不變的List，因爲它可以直接返回內部維護的結構。它也是不可變的List的默認構建器（因此確實可以合理預期具有恆定時間附加）。如果您調用toList，然後再將一個元素附加到緩衝區中，則相對於緩衝區中當前元素數量，需要線性時間來重新創建新結構，因爲它不能再更改導出的列表。

MutableList與LinkedList內部工作原理相反，（公開，不喜歡::），它知道它的元素和繼任者（如::）的可變鏈表實現。 MutableList也保留指向第一個和最後一個元素的指針，但是toList以線性時間返回，因爲結果List從LinkedList構造而成。因此，在導出List之後，不需要重新初始化緩衝區。

根據您的要求，我會說ListBuffer和MutableList是等效的。如果你想在某個時候導出他們的內部列表，那麼問問自己你想要的開銷：當你導出列表，然後在沒有開銷的情況下，如果你繼續進行突變緩衝區（然後去MutableList），或者只有當你改變再次緩衝，並且在輸出時沒有（然後去ListBuffer）。

我的猜測是在2.8集合檢修中，MutableList先於ListBuffer和整個Builder系統。實際上，MutableList在collection.mutable包中主要是有用的：它有一個可以在不變的情況下返回的方法，因此可以有效地用作內部維護LinkedList的所有結構的委託構建器。

所以我也推薦ListBuffer，因爲它可能也會比「純粹可變」結構如MutableList和LinkedList得到關注和優化。

來源

2011-04-22 09:06:13

我不認爲ListBuffer允許定時獲取/刪除最後一個元素！見[ListBuffer.scala]（https://github.com/scala/scala/blob/2.10.x/src/library/scala/collection/mutable/ListBuffer.scala） – 2013-12-13 09:06:36

你說得對 - 看起來沒有。太糟糕了，因爲它很容易。 – 2013-12-13 09:20:27

這給你一個性能特點的概述：http://www.scala-lang.org/docu/files/collections-api/collections.html;有趣的是，MutableList和ListBuffer在那裏沒有差異。 MutableList的文檔說它在內部用作Stack和Queue的基類，所以從用戶的角度來看，ListBuffer可能更多是官方的類？

來源

2011-03-27 05:57:05

你想要的清單（爲什麼名單？）是可增長和收縮，並且要不斷追加和預先準備。那麼，Buffer，一個特質，不斷附加和前置，與其他大多數操作線性。我猜ListBuffer，一個實現了Buffer的類，持續時間去除了第一個元素。

所以，我自己的建議是ListBuffer。

來源

2011-03-27 16:21:04

首先，讓我們去了一些相關類型的斯卡拉

List - 不可變集合。遞歸實現，即。即列表的一個實例具有兩個主要元素頭部和尾部，其中尾部引用另一個List。

List[T] 
    head: T 
    tail: List[T] //recursive

LinkedList - 定義爲一系列鏈接的節點，其中每個節點包含一個值和一個指針到下一個節點一個可變的集合。

Node[T] 
    value: T 
    next: Node[T] //sequential 

LinkedList[T] 
    first: Node[T]

與命令式語言中更爲標準的LinkedList相比，List是一種功能性數據結構（不變性）。現在

，讓我們看看

ListBuffer - 由List支持一個可變的緩衝區實現。

MutableList - 基於鏈表的實現（會更自我解釋，如果它被命名爲LinkedListBuffer代替）

They both offer similar complexity bounds on most operations.

但是，如果你從一個MutableList請求List，那麼它必須將現有的線性表示轉換爲遞歸表示，這需要@ Jean-Philippe Pellet指出的O（n）。但是，如果您從MutableList請求Seq，則複雜度爲O（1）。

所以，IMO的選擇範圍縮小到您的代碼的細節和您的偏好。雖然，我懷疑有更多List和ListBuffer在那裏。

來源

2011-12-28 01:43:00 smartnut007

請注意，ListBuffer是final/sealed，而您可以擴展MutableList。根據您的應用程序，可擴展性可能會有所幫助。

來源

2015-02-24 11:39:08 Herc

MutableList和ListBuffer之間的區別

回答

相關問題